③線性代數(shù)方程求解計(jì)算

在自然科學(xué)和工程技術(shù)的許多實(shí)際問題中，如結(jié)構(gòu)分析、大地測(cè)量、網(wǎng)絡(luò)分析、數(shù)據(jù)分析、最優(yōu)化等問題中常常遇到線性代數(shù)方程組求解問題。數(shù)學(xué)中，例如求解非線性方程組或微分方程數(shù)值解問題也常轉(zhuǎn)化為線性代數(shù)方程組求解問題。早在中國(guó)古代的《九章算術(shù)》中，就已經(jīng)有了解線性方程組的消元法。到19世紀(jì)初，西方又有了高斯消元法。然而求解未知數(shù)很多的大型線性代數(shù)方程組，則是在20世紀(jì)中葉電子計(jì)算機(jī)問世以后才成為可能。如何利用計(jì)算機(jī)更精確、更有效地解大型線性代數(shù)方程組是計(jì)算數(shù)學(xué)研究中的基本性的重要課題之一。
線性代數(shù)方程組數(shù)值解法可分為二大類，即直接法和迭代法，現(xiàn)簡(jiǎn)介如下。

1.解線性方程組的直接法

解線性方程組 Ax=F的直接法是指經(jīng)過有限步運(yùn)算后能求得方程組精確解的方法。如果A的行列式detA≠0,按克拉默法則，線代數(shù)方程的解x_j=detA_j/detA，式中A_j是把A中的第j列元素用自由項(xiàng)？₁,？₂,…，？_n代替后所得的矩陣?？死▌t之功效主要在于理論意義，若用于數(shù)值求解，則因n+1個(gè)n階行列式求值的計(jì)算量很大而不實(shí)用。但由于實(shí)際計(jì)算中舍入誤差是客觀存在的，因而使用這類方法也只能得到近似解。目前較實(shí)用的直接法是古老的高斯消去法的變形，即主元素消去法及矩陣的三角分解法。引進(jìn)選主元的技巧是為了控制計(jì)算過程中舍入誤差的增長(zhǎng)，減少舍入誤差的影響。一般說來，列主元消去法及列主元三角分解法是數(shù)值穩(wěn)定的算法，它具有精確度較高、計(jì)算量不大和算法組織容易等優(yōu)點(diǎn)，是目前計(jì)算機(jī)上解中、小型稠密矩陣方程組可靠而有效的常用方法。

2.解線性方程組的迭代法

解線性方程組的迭代法是用某種極限過程去逐步逼近線性方程組精確解的方法，即是從一個(gè)初始向量x⁽⁰⁾出發(fā)，按照一定的迭代格式產(chǎn)生一個(gè)向量序列{x^(k)}，構(gòu)造一個(gè)向量的無窮序列，使其收斂到方程組 Ax=F的解。熟知的簡(jiǎn)單迭代法、高斯－賽德爾迭代法、松弛法等都屬此類。迭代法的優(yōu)點(diǎn)是所需計(jì)算機(jī)存儲(chǔ)單元少，程序設(shè)計(jì)簡(jiǎn)單，原始系數(shù)矩陣在計(jì)算過程中始終不變等。迭代法是解大型稀疏矩陣方程組的重要方法，但存在收斂性及收斂速度等問題。
上述兩種方法各有優(yōu)缺點(diǎn)，直接法普遍適用，但要求計(jì)算機(jī)有較大的存儲(chǔ)量，迭代法要求的存儲(chǔ)量較小，但必須在收斂性得以保證的情況下才能使用。直接法可以求得精確解是指就計(jì)算公式而言保證得到精確解，但計(jì)算機(jī)計(jì)算過程中的舍入誤差是不可避免的，要求這種誤差對(duì)解的精度影響會(huì)不會(huì)太大，也就是計(jì)算的穩(wěn)定性，是要考慮的問題。對(duì)于迭代法，其收斂性則是要考慮的問題。
所以，不論是直接法還是迭代法都要根據(jù)方程組的具體性質(zhì)，例如系數(shù)矩陣的稀疏狀態(tài)、正定性、對(duì)角優(yōu)勢(shì)等等，選擇計(jì)算方法和采用諸如稀疏技術(shù)、加速收斂等相應(yīng)措施，才能更為有效地利用計(jì)算機(jī)得出比較滿意的結(jié)果。

④非線性代數(shù)方程求解計(jì)算

當(dāng)f(x)中含有超越函數(shù)（如三角函數(shù)、指數(shù)和對(duì)數(shù)函數(shù)等不能用有限次加、減、乘、除、乘方、開方 運(yùn)算表示的函數(shù)）或高次多項(xiàng)式時(shí)，f(x)=0稱為非線性方程。此類方程除少數(shù)情形外，多數(shù)情況中只能求取近似解。在科學(xué)研究與工程技術(shù)中，經(jīng)常會(huì)遇到求解這類非線性方程的問題。
非線性問題是現(xiàn)代數(shù)學(xué)中的一個(gè)非常活躍的領(lǐng)域，大量的非線性問題，如非線性有限元問題、經(jīng)濟(jì)與非線性規(guī)劃問題以及物理、化學(xué)、流體力學(xué)中許多關(guān)鍵問題的解決，往往歸結(jié)為求解某些特定的非線性方程；在非線性力學(xué)中，有多種類型的非線性，如材料非線性、幾何非線性、接觸非線性等；非線性方程的求解也是科學(xué)與工程計(jì)算中一個(gè)常見且重要的問題。然而除了一些非常的特殊情形外，直接法很難求解非線性方程。對(duì)于實(shí)際問題，很多情況下并不必求出方程的真實(shí)解，只需求得一個(gè)近似值，當(dāng)然此近似值與真實(shí)解之間的誤差應(yīng)該控制在實(shí)際問題所能允許的范圍之內(nèi)。近似解可以通過數(shù)值方法來獲得，所以研究非線性方程的數(shù)值解法有著重要的理論意義和實(shí)際應(yīng)用價(jià)值。
對(duì)于非線性函數(shù)f(x)，如在x=r時(shí)，有f(r)=0，那么稱x=r為函數(shù)f(x)的零點(diǎn)，也叫做方程的根。求解方程就是計(jì)算該方程的所有零點(diǎn)。
非線性方程求零點(diǎn)需要解決的問題有：1. 零點(diǎn)的存在性：方程是否有零點(diǎn)，如果有零點(diǎn)，有幾個(gè)零點(diǎn)？ 2. 零點(diǎn)的隔離：找出有零點(diǎn)的區(qū)域，把有零點(diǎn)區(qū)域分成較小的子區(qū)域，每個(gè)子區(qū)域有一個(gè)零點(diǎn)，將有零點(diǎn)區(qū)域內(nèi)的任一點(diǎn)都看成該零點(diǎn)的一個(gè)初始近似值；3. 零點(diǎn)的精確化：對(duì)已知零點(diǎn)的初始近似值，逐步精確化，以得到非線性方程的可接受近似解。
現(xiàn)在有許多算法可用來求解非線性方程，如二分法簡(jiǎn)單易行，但收斂較慢，僅有線性收斂速度，而且該方法不能用于求偶數(shù)重根或復(fù)根，但可以用來確定迭代法的初始值；牛頓法是方程求根中常用的一種迭代方法，除具有簡(jiǎn)單迭代法的優(yōu)點(diǎn)外，還具有二階收斂速度，但牛頓法對(duì)初始值選取比較苛刻（必須充分靠近方程的根），否則牛頓法可能不收斂；弦截法是牛頓法的一種修改，雖然比牛頓法收斂慢，但因它不需計(jì)算函數(shù)的導(dǎo)數(shù)，故有時(shí)寧可用弦截法而不用牛頓法，弦截法也要求初始值必須選取得充分靠近方程的根，否則也可能不收斂。
求解一元非線性方程f(x)=0的二分法，是一種簡(jiǎn)單有效的方法，逐次把有根區(qū)間分半，直到找到根或有根區(qū)間的長(zhǎng)度小于給定精度為止。
在二分法中，假定非線性函數(shù)f(x)在區(qū)間(c，d)上連續(xù)。如果存在兩個(gè)實(shí)數(shù)a和b屬于區(qū)間(c，d)，使得f(a)*f(b)<0成立，也就是說f(a)和f(b)異號(hào)，說明在區(qū)間(a，b)內(nèi)至少有一個(gè)零點(diǎn)，即含該方程的一個(gè)解。然后，我們計(jì)算f[(a+b)/2]。此時(shí)，假設(shè)f(a)<0，f(b)>0成立。我們可以根據(jù)f[(a+b)/2]的值來判斷方程解的位置：如果f[(a+b)/2]=0，該點(diǎn)就是零點(diǎn)，為所求的解；如果f[(a+b)/2]<0，則表示在區(qū)間 ((a+b)/2, b) 內(nèi)有零點(diǎn)，(a+b)/2=>a，重復(fù)前面的步驟來進(jìn)行判斷；如果f[(a+b)/2]>0，則表示在區(qū)間 (a，(a+b)/2) 內(nèi)有零點(diǎn)， b=> (a+b)/2，重復(fù)前面的步驟來進(jìn)行判斷。
這樣，通過上述步驟就可以不斷接近零點(diǎn)。由于非線性方程在很多時(shí)候都沒有精確解，因此我們可以設(shè)置一個(gè)精度，當(dāng)f(x)小于該精度時(shí)就認(rèn)為找到了零點(diǎn)，也就是找到了方程的解。這種通過每次把f(x)的零點(diǎn)所在區(qū)間收縮一半的方法，使區(qū)間的兩個(gè)端點(diǎn)逐步迫近函數(shù)的零點(diǎn)，以求得零點(diǎn)的近似值。
非線性方程的數(shù)值算法很多，像解線性方程組一樣，有直接法和迭代法之分，但主要的方法是迭代法。迭代法是一種逐次逼近的方法。首先要求所構(gòu)造的迭代公式收斂，即導(dǎo)數(shù)的絕對(duì)值小于1，且其值越小收斂速度越快，此法用的比較廣泛，速度比較快。使用這一方法一般至少要知道根的一個(gè)近似值x₀，然后將原方程f(x)=0改變成與它同解但便于迭代的形式x=P(x)，利用迭代公式x_k+1=P(x_k)，k=0，1，2，……，就能求出一系列逐步精確的近似值。例如常用的迭代法有：
1、牛頓迭代法：給出x₀為初始近似值；
2、割線迭代法，需給出x₀，x₁為兩個(gè)初始近似值。
評(píng)價(jià)一個(gè)迭代公式的優(yōu)劣，除去收斂條件之外，主要是看它的效能指標(biāo)，即達(dá)到規(guī)定的精確度所花費(fèi)的代價(jià)。因此如何構(gòu)造收斂的迭代公式，分析公式的收斂速度和收斂條件，以及加快收斂的技術(shù)，這些都是迭代法要研究的課題。牛頓迭代具有較高的收斂速度和簡(jiǎn)單靈活等優(yōu)點(diǎn)，而且可以推廣到求解非線性方程組，擬牛頓法就是具有較高效能指標(biāo)的求解非線性方程組的通行方法。此外還有二次插值法、切比雪夫迭代法及艾特肯加速法等。
牛頓弦截法是牛頓法的一種改進(jìn)，雖然比牛頓法收斂慢，但因它不需計(jì)算函數(shù)的導(dǎo)數(shù)，故有時(shí)寧可用弦截法而不用牛頓法，弦截法也要求初始值必須選取得充分靠近方程的根，否則也可能不收斂。弦截法是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法，在迭代過程中不僅用到前一步 x_k處的函數(shù)值，而且還使用x_k-1處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。
為避免計(jì)算函數(shù)的導(dǎo)數(shù) f′(x_k)，使用差商

？替代牛頓公式中的導(dǎo)數(shù) f′(x_k) ,便得到迭代公式

？稱為弦截迭代公式，相應(yīng)的迭代法稱為弦截法?？梢宰C明，弦截法具有超線性收斂，它與前面介紹的一般迭代法一樣都是線性化方法。一般迭代法在計(jì)算x_k+1時(shí)只用到前一步的值x_k，故稱之為單點(diǎn)迭代法；而弦截法在求x_k+1時(shí)要用到前兩步的結(jié)果x_k-1和x_k，使用這種方法必須給出兩個(gè)初始近似根x₀ , x₁，這種方法稱為多點(diǎn)迭代法。

在科學(xué)研究和工程設(shè)計(jì)中，經(jīng)常遇到求解由非線性代數(shù)方程組構(gòu)建的數(shù)學(xué)模型，這已不是一元非線性，而是多元非線性問題，和一元非線性相比，更加復(fù)雜多變，可以說求解時(shí)遇到的困難更多、更大。
為簡(jiǎn)單和統(tǒng)一起見，我們用函