用迭代法求公切線

趙小香

用迭代法求公切線

（廣西師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 廣西·桂林 541004）

摘 要 根據(jù)牛頓切線法求方程的根的思想，結(jié)合2008年數(shù)學(xué)建模A題，運(yùn)用迭代法求兩凸集（橢圓）的公切線，算法簡(jiǎn)潔實(shí)用，可操作性強(qiáng)。并證明了算法對(duì)公切線的收斂性和收斂速度。

關(guān)鍵詞 迭代法 公切線 凸集分離 數(shù)學(xué)建模

中圖分類號(hào)：O182 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.16400/j.cnki.kjdks.2015.05.014

Seek Common Tangent with the Iterative Method

ZHAO Xiaoxiang

（School of Mathematics and Statistics， Guangxi Normal University，

Guilin， Guangxi Normal University， Guilin， Guangxi 541004）

Abstract According to Newton's equation of the tangent method the root of thinking， combined with mathematical modeling A title in 2008， using the iterative method for two convex sets （oval） common tangent， the algorithm is simple and practical， workable. And proved common tangent algorithm convergence and convergence rate.

Key words iterative method; common tangent; separation of convex sets; mathematical modeling

0 引言

隨著計(jì)算機(jī)加入科學(xué)研究的行列，迭代算法作為計(jì)算機(jī)能執(zhí)行的有效算法，在解決實(shí)際問題中起著越來越重要的作用。區(qū)間二分法、牛頓法等都是經(jīng)典的迭代法。

2008年高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽甲組A題《數(shù)碼相機(jī)定位》問題的一種解決思路是通過求公切線交點(diǎn)的方法來確定圓心。而求兩個(gè)橢圓（或R2內(nèi)任意有界閉凸子集）的公切線就可以用迭代算法來實(shí)現(xiàn)。尤其是在離散（橢圓由相片給出，而相片只能分解為離散的像素點(diǎn)）的情況下，迭代算法更加適合于計(jì)算機(jī)的實(shí)現(xiàn)。

1 數(shù)碼相機(jī)定位

08數(shù)模A題的數(shù)碼相機(jī)定位問題給出了標(biāo)靶以及標(biāo)靶在相機(jī)中的像，如圖1、2要求設(shè)計(jì)算法求出相片中圓的圓心，以建立像坐標(biāo)系到世界坐標(biāo)系的點(diǎn)點(diǎn)對(duì)應(yīng)，從而完成系統(tǒng)標(biāo)定。具體題目見文獻(xiàn)[1]。

圖1 標(biāo)靶 ? ? ? 圖2 標(biāo)靶在相機(jī)中的像

公切線交點(diǎn)的方法是指根據(jù)直線的像還直線的原理，作圓A與圓C、圓A與圓E的外公切線，如圖3，四條切線有四個(gè)交點(diǎn)，構(gòu)成正方形，正方形對(duì)角線交點(diǎn)即為圓A的圓心。在相片中，只需求出變形后的圓A與圓C、圓A與圓E的外公切線，即可確定圓心。圖4。

圖3 標(biāo)靶中的公切線 圖4 像中的公切線

所以問題可轉(zhuǎn)化為設(shè)計(jì)算法求兩圓的外公切線。而本文主要研究如何用迭代法來求兩圓的公切線。

2 外公切線算法

求兩個(gè)橢圓（或R2內(nèi)任意有界閉凸子集）的外公切線的迭代算法，具體操作步驟如下：

（1）對(duì)給定的兩個(gè)橢圓A、B，分別任意給出一條切線和，切橢圓A，切橢圓B，兩切線在兩圓的同側(cè)，且只與一圓線切，如圖5。

圖5 初始切線 ? ? ? ? ? ?圖6 第一次迭代

（2）過和的交點(diǎn)做和的角平分線，如圖6。

（3）將平移至與圓相切，如果能與兩圓都相切，即為所求公切線，則停止。若不能與兩圓都相切，將平移至較近的圓，并取代與該圓相切的直線。如圖7，平移后與圓B相切，且用取代。

（4）過和的交點(diǎn)做和的角平分線，如圖8。

（5）將平移至于一圓相切，如果能與兩圓都相切，即為所求公切線，則停止。若只能與一圓相切，將平移至該圓，并取代與該圓相切的直線。如圖9，平移后與圓A相切，且用取代。

圖7 調(diào)整初始切線 圖8 第二次迭代

圖9 調(diào)整初始切線 圖10 第三次迭代

（6）過和的交點(diǎn)做和的角平分線，如圖10，重復(fù)以上過程。

（7）當(dāng)與兩圓相切或與兩圓距離達(dá)到足夠小的精度時(shí)，停止。

在實(shí)際操作中，做兩直線的角平分線可改為取兩直線斜率之和的一半為斜率做直線，這樣并不影響收斂性和收斂速度。

定理1 上述步驟給出的平分直線的斜率收斂于兩橢圓的外公切線的斜率。且收斂速度為（）。

證明：設(shè)的斜率為，的斜率為，兩橢圓公切線的斜率為，<<則的斜率 = ，∣∣≤。

不妨設(shè)取代了，則根據(jù)的取法，有<<。那么的斜率 = ， 從而∣∣≤≤。

同理，∣∣≤， ≥2。

即上述步驟給出的平分直線的斜率收斂于兩橢圓的外公切線的斜率。且收斂速度為（）。

3 算法實(shí)現(xiàn)

在上述迭代法實(shí)現(xiàn)應(yīng)用過程中，我們一般適當(dāng)調(diào)整坐標(biāo)系，使得所求公切線的斜率大致在0.5到1.5之間，并選擇合理的初值，使得每次所選的角平分線是兩橢圓同側(cè)的直線，而不是另一條將兩圓分開的角平分線，如圖11。同時(shí)，也可減少計(jì)算精度帶來的誤差。

圖11 適當(dāng)選取初始切線的角平分線

以08數(shù)模A題為例，我們給出用matlab編程實(shí)現(xiàn)上述迭代算法的具體過程。

按照上述方法繼續(xù)迭代，直到達(dá)到允許精讀。由圖12-17 可以看出，當(dāng)?shù)奈宕我院?，就已?jīng)相當(dāng)精確。

值得注意的是，同樣的思路可以用來求內(nèi)公切線，進(jìn)而可以將兩個(gè)凸集分離。

圖12-17 matlab編程實(shí)現(xiàn)迭代算法的過程

參考文獻(xiàn)

[1] 華東師范大學(xué)數(shù)學(xué)系編.數(shù)學(xué)分析（上）第四版[M].北京：高等教育出版社，2010.7.

[2] 全國大學(xué)生數(shù)學(xué)建模競(jìng)賽.http：//www.mcm.edu.cn/.2008.9.