Kaya naman sinusunod iyon α ≈ | φ ′ (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Kaya, para sa paraan upang magtagpo, ito ay sapat na ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

Pangkalahatang algorithm ng sunud-sunod na pagtatantya[ | ]

Bilang inilapat sa pangkalahatang kaso ng mga equation ng operator, ang pamamaraang ito ay tinatawag paraan ng sunud-sunod na approximation o simpleng paraan ng pag-ulit. Gayunpaman, ang equation ay maaaring mabago sa contraction mapping , na may parehong ugat, sa iba't ibang paraan. Nagbibigay ito ng ilang partikular na pamamaraan na may parehong linear at mas mataas na mga rate ng convergence.

Tulad ng inilapat sa SLAU[ | ]

Isaalang-alang ang sistema:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+ \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(array))\kanan.)

Para dito, ang umuulit na pagkalkula ay magiging ganito:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2 ) ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\ dulo (array))\kanan)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_ ( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\ kanan )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left ( (\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

Ang pamamaraan ay magtatagpo sa isang linear rate kung ‖ a 1 + 1 … a 1 n ⋮ 1 naging ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Ang mga double vertical bar ay nangangahulugang ilang matrix norm.

Solusyon ng equation f(x)=0 sa pamamagitan ng Newton's method, initial approximation: x 1 =a.

Paraan ni Newton (paraan ng tangent)[ | ]

Isang-dimensional na kaso[ | ]

Pag-optimize ng pagbabago ng orihinal na equation f (x) = 0 (\displaystyle f(x)=0) sa contraction mapping x = φ (x) (\displaystyle x=\varphi (x)) ay nagbibigay-daan sa iyo upang makakuha ng isang paraan na may isang parisukat na rate ng convergence.

Para maging pinakamabisa ang pagmamapa, kinakailangan na sa punto ng susunod na pag-ulit x ∗ (\displaystyle x^(*)) isinagawa φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Maghahanap tayo ng solusyon sa equation na ito sa anyo φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), pagkatapos:

Gamitin natin kung ano f (x) = 0 (\displaystyle f(x)=0), at makuha namin ang panghuling formula para sa α (x) (\displaystyle \alpha (x)):

Sa pag-iisip na ito, ang contraction function ay kukuha ng form:

Pagkatapos ay ang algorithm para sa paghahanap ng isang numerical na solusyon sa equation f (x) = 0 (\displaystyle f(x)=0) bumababa sa isang umuulit na pamamaraan ng pagkalkula:

Paulit-ulit na Pamamaraan

Ipinapalagay ng mga iterative na pamamaraan ang pagpapatupad ng sumusunod na tatlong yugto: pagbuo ng isang umuulit na proseso na nagtatagpo sa eksaktong solusyon para sa pagkalkula ng sunud-sunod na mga pagtatantya (ibig sabihin, pagbuo ng isang pagkakasunud-sunod ng mga vector na nagtatagpo sa eksaktong solusyon ; pagpapasiya ng convergence criterion ng prosesong ito, na nagbibigay-daan sa pagtukoy sa sandali ng pagkamit ng kinakailangang katumpakan; pag-aaral ng rate ng convergence at optimization ng umuulit na proseso upang mabawasan ang bilang ng mga operasyon na kinakailangan upang makamit ang kinakailangang katumpakan.

Ginagawang posible ng mga paulit-ulit na pamamaraan na makakuha ng solusyon na may paunang natukoy na katumpakan, kung ang convergence ng pamamaraan ay napatunayan. Ang mga iterative na pamamaraan ay hindi nagbibigay ng isang mahigpit na eksaktong solusyon, dahil ito ay nakamit bilang isang limitasyon ng isang pagkakasunud-sunod ng mga vectors. Ang direktang paraan sa pangkalahatan ay nagbibigay ng eksaktong solusyon, ngunit dahil sa mga error sa rounding na nagaganap sa lahat ng mga computer, hindi ito maabot, at isang priori mahirap pa ngang tasahin kung gaano kaiba ang solusyong ito sa eksaktong isa. Kaugnay ng nasa itaas, minsan ginagawang posible ng mga umuulit na pamamaraan na makakuha ng solusyon na may higit na katumpakan kaysa sa mga direktang solusyon.

Isaalang-alang ang ilang umuulit na pamamaraan para sa paglutas ng mga linear na equation.

Simpleng paraan ng pag-ulit

Sa simpleng paraan ng pag-ulit, sistema (2.1) ng mga linear algebraic equation palakol = b ay binabawasan sa isang katumbas na sistema ng anyo

Ang solusyon ng system (2.9) at, dahil dito, ang solusyon ng orihinal na sistema (2.1) ay hinahangad bilang limitasyon ng pagkakasunud-sunod ng mga vectors para sa :

k = 0, 1, 2,…,(2.10)

kung saan ang paunang pagtatantya para sa vector ng solusyon.

Ang isang sapat na kondisyon para sa convergence ng simpleng paraan ng pag-ulit ay tinutukoy ng sumusunod na theorem.

TEOREM 1. Kung ang anumang pamantayan ng matrix na naaayon sa itinuturing na pamantayan ng vector ay mas mababa sa pagkakaisa (), kung gayon ang pagkakasunud-sunod sa simpleng paraan ng pag-ulit ay nagtatagpo sa eksaktong solusyon ng system (2.9) sa bilis na hindi bababa sa rate ng isang geometric na progression na may denominator para sa anumang paunang pagtataya .

PATUNAY. Upang patunayan ang teorama, ipinakilala namin ang isang error. Ang pagbabawas ng pagkakapantay-pantay (2.10) mula sa kaugnayan, makakakuha tayo ng . Ang pagpasa sa mga pamantayan, mayroon tayo

Tandaan na ang hindi pagkakapantay-pantay mula sa nakaraang expression ay ang kondisyon ng pagkakapare-pareho para sa pamantayan ng matrix at vector. Kung ang , pagkatapos ay para sa anumang paunang vector ng error (o kung hindi man, para sa anumang paunang vector ), ang rate ng error ay may posibilidad na maging zero nang hindi mas mabagal kaysa sa isang geometric na pag-unlad na may denominator .

Kung pipiliin natin ang pamantayan bilang pamantayan ng matrix o pagkatapos ay upang malutas ang tanong ng convergence ng simpleng paraan ng pag-ulit, ang isa ay maaaring gumamit ng corollary mula sa Theorem 1: ang simpleng paraan ng pag-ulit ay nagtatagpo kung ang isa sa mga sumusunod na kondisyon ay nasiyahan para sa matrix:

, i =1,2, …, n,

, j = 1, 2, …, n.(2.11)

Ang pinakasimpleng at pinakakaraniwang paraan upang dalhin ang system Ax=b sa anyo (2.9), na maginhawa para sa mga pag-ulit, ay ang pagpili ng mga elemento ng dayagonal, sa bawat isa i-th ang equation ay nalutas na may kinalaman sa i-th hindi alam:

, i = 1, 2, …, n, (2.12)

at ang simpleng paraan ng pag-ulit ay maaaring isulat bilang

Ang matrix pagkatapos ay may anyo

.

Ang elemento ng matrix na ito ay maaaring isulat bilang nasaan ang simbolo ng Kronecker. Sa kasong ito, ang isang sapat na kondisyon para sa convergence ng simpleng paraan ng pag-ulit ay maaaring mabalangkas bilang kondisyon para sa pangingibabaw ng mga elemento ng dayagonal ng matrix. PERO, na sumusunod mula sa (2.11) at ang notasyon ng matrix , i.e.

i = 1, 2, …, n.

Muli naming binibigyang-diin na ang mga itinuturing na anyo ng kondisyon para sa convergence ng paraan ng pag-ulit ay sapat lamang. Ang kanilang pagpapatupad ay ginagarantiyahan ang convergence ng pamamaraan, ngunit ang kanilang pagkabigo sa pangkalahatang kaso ay hindi nangangahulugan na ang simpleng paraan ng pag-ulit ay nag-iiba. Ang isang kinakailangan at sapat na kundisyon para sa convergence ng simpleng paraan ng pag-ulit ay ang kundisyon na ang bahagi ng integer (kung saan ang pinakamataas na modulo eigenvalue ng matrix PERO); ang kundisyong ito ay bihirang ginagamit sa computational practice.

Bumaling tayo sa tanong ng pagtantya ng pagkakamali ng solusyon. Ang interes ay dalawang relasyon para sa pagtatantya ng error ng solusyon: ang una ay nauugnay ang pamantayan ng error sa pamantayan ng pagkakaiba ng dalawang sunud-sunod na pagtatantya at maaaring magamit upang tantyahin ang error lamang sa proseso ng mga kalkulasyon; ang pangalawa ay nauugnay ang pamantayan ng error sa mga pamantayan ng vector ng paunang pagtatantya at ang vector ng libreng termino sa system (2.9). Ang mga kinakailangang relasyon ay ibinibigay ng sumusunod na dalawang theorems.

THEOREM 2. Kung anumang norm ng matrix na pare-pareho sa itinuturing na norm ng vector X

. (2.13)

PATUNAY. Ibawas natin ang pagkakapantay-pantay (2.10) sa pagkakapantay-pantay:

Ibinabawas mula sa parehong bahagi ang approximation value , binabago namin ang ratio na ito sa form

Ang pagpasa sa mga pamantayan, nakukuha natin

Dahil, sa pamamagitan ng hypothesis ng theorem,

Gamit ang kaugnayan kung saan sinusundan iyon sa wakas nakuha namin:

TEOREM 3. Kung ang anumang pamantayan ay isang matrix na naaayon sa itinuturing na pamantayan ng vector X, mas mababa sa isa (), pagkatapos ay magaganap ang sumusunod na pagtatantya ng error:

Gumawa tayo ng dalawang pangungusap. Una, ang kaugnayan (2.13) ay maaaring isulat bilang

na ginagawang posible na makakuha ng pagtatantya ng error batay sa mga resulta ng unang dalawang pag-ulit. Una, kapag ginagamit ang paraan ng pag-ulit, minsan ay inirerekomenda na gamitin ang pamantayan ng pagkakaiba ng dalawang magkasunod na pagtatantya bilang isang pagtatantya ng error sa pagkalkula. Ito ay sumusunod mula sa mga ugnayan para sa error na ito ay hindi totoo sa pangkalahatang kaso. Kung ang pamantayan ay malapit sa pagkakaisa, kung gayon ang koepisyent sa ay maaaring medyo malaki.

Ang mga pagkakamali ng sunud-sunod na pag-ulit ay nauugnay sa kaugnayan

mga. linearly nagbabago ang error sa isang hakbang. Ang pamamaraan ay sinasabing mayroon linear convergence o first order convergence. Gayunpaman, ang bilang ng mga pag-ulit na kinakailangan upang makamit ang kinakailangang katumpakan ay depende sa halaga at paunang pagtatantya ng .

Kaya, gamit ang simpleng paraan ng pag-ulit bilang isang halimbawa, ang tatlong yugto ng mga pamamaraan ng umuulit ay ipinapakita: pagbuo ng isang pagkakasunod-sunod ng mga vector na nabuo ng formula (1.10); pagpapasiya ng kondisyon ng convergence ayon sa Theorem 1 at isang pagtatantya ng rate ng convergence gamit ang Theorems 2 at 3.

Paraan ng Seidel

Ang simpleng paraan ng pag-ulit ay hindi gumagamit ng tila malinaw na posibilidad ng pagpapabuti ng convergence ng proseso ng umuulit - ang agarang pagpapakilala ng mga bagong kalkuladong bahagi ng vector sa pagkalkula. Ang posibilidad na ito ay ginagamit sa umuulit na paraan ng Seidel. Ang umuulit na proseso para sa system (2.9) ay isinasagawa sa kasong ito ayon sa kaugnayan

i = 1, 2, …, n (2.14)

o para sa system (1.1)

Nang hindi naglalarawan ng mga detalye, napapansin namin na ang Seidel iteration method ay kadalasang humahantong sa mas mabilis na convergence kaysa sa simpleng paraan ng iteration. Gayunpaman, may mga kaso kung saan ang paraan ng pag-ulit ng Seidel ay nagtatagpo nang mas mabagal kaysa sa simpleng paraan ng pag-ulit, at kahit na ang mga kaso kung saan ang paraan ng pag-ulit ng simpleng pag-uulit ngunit nag-iiba ang paraan ng pag-ulit ng Seidel.

Tandaan na ang paraan ng Seidel ay nagtatagpo, kung matris PERO positibong tiyak at simetriko.

Ipakita natin na ang paraan ng pag-ulit ng Seidel ay katumbas ng ilang simpleng paraan ng pag-ulit na may espesyal na itinayong matrix at vector na may kaugnayan (2.10). Upang gawin ito, isinusulat namin ang system (2.14) sa form Matrix (E-H) ay isang mas mababang triangular matrix na may mga elementong dayagonal na katumbas ng isa. Samakatuwid, ang determinant ng matrix na ito ay non-zero (katumbas ng isa) at mayroon itong inverse matrix. Pagkatapos

Kung ikukumpara ang ugnayang ito sa solusyon (2.10), maaari nating tapusin na ang Seidel iteration method ay talagang katumbas ng simpleng paraan ng pag-ulit sa kahulugan na, upang maitatag ang kundisyon at ang convergence criterion para sa Seidel iteration method, magagamit ang mga theorems na ibinigay. para sa simpleng paraan ng pag-ulit, kung itinakda namin Ang umuulit na proseso para sa system (2.12) ay maaari ding isulat sa isang mas pangkalahatang anyo, ibig sabihin

Hayaang magbigay ng isang sistema ng n algebraic equation na may n hindi alam:

Simpleng algorithm ng pamamaraan ng pag-ulit:

Tandaan na dito at sa sumusunod, tinutukoy ng subscript ang kaukulang bahagi ng vector ng mga hindi alam, at ang superscript ay tumutukoy sa numero ng pag-ulit (approximation).

Pagkatapos ay nabuo ang isang cyclic na proseso ng matematika, na ang bawat cycle ay kumakatawan sa isang pag-ulit. Bilang resulta ng bawat pag-ulit, isang bagong halaga ng vector ng mga hindi alam ang nakuha. Upang ayusin ang umuulit na proseso, isinusulat namin ang system (1) sa form sa itaas. Sa kasong ito, ang mga termino sa pangunahing dayagonal ay na-normalize at nananatili sa kaliwa ng pantay na tanda, habang ang iba ay inililipat sa kanang bahagi. Pinababang sistema ng mga equation mukhang:

pansinin mo yan ay hindi kailanman maaabot, gayunpaman, sa bawat kasunod na pag-ulit, ang vector ng mga hindi alam ay papalapit nang papalapit sa eksaktong solusyon.

12. Ang pangunahing umuulit na formula na ginamit sa simpleng paraan ng pag-ulit para sa paglutas ng isang hindi linear na equation:

13. Pamantayan para sa paghinto ng umuulit na proseso sa simpleng paraan ng pag-ulit para sa paglutas ng isang nonlinear equation:

Ang umuulit na proseso ay nagtatapos kung para sa bawat i-th na bahagi ng vector ng mga hindi alam ang kondisyon para sa pagkamit ng katumpakan ay nasiyahan.
pansinin mo yan eksaktong solusyon sa simpleng paraan ng pag-ulit ay hindi kailanman maaabot, gayunpaman, sa bawat kasunod na pag-ulit, ang vector ng mga hindi alam ay papalapit nang papalapit sa eksaktong solusyon

14. Pamantayan para sa pagpili ng auxiliary function na F(x) para sa pag-ulit na segment ng interval :

Kapag nagsasagawa ng pagsusulit sa matematika para sa paglutas ng simpleng paraan ng pag-ulit, dapat munang suriin ang kundisyon ng convergence. Para sa convergence ng pamamaraan, kinakailangan at sapat na sa matrix A ang mga ganap na halaga ng lahat ng mga elemento ng dayagonal ay mas malaki kaysa sa kabuuan ng mga module ng lahat ng iba pang mga elemento sa kaukulang hilera:

Kahinaan ng mga umuulit na pamamaraan Ito ay isang medyo mahigpit na kondisyon ng convergence, na malayo sa pagiging nasiyahan para sa lahat ng mga sistema ng mga equation.

Kung ang kondisyon ng convergence ay nasiyahan, pagkatapos ay sa susunod na yugto kinakailangan upang itakda ang paunang pagtatantya ng vector ng mga hindi alam, na kadalasan ay ang zero vector:

15. Ang pamamaraang Gauss na ginamit upang malutas ang mga sistema ng mga linear na equation ay nagbibigay ng:

Ang pamamaraan ay batay sa matrix transformation sa triangular form. Ito ay nakakamit sa pamamagitan ng sunud-sunod na pag-aalis ng mga hindi alam mula sa mga equation ng system.

Ang paraan ng simpleng pag-ulit, na tinatawag ding paraan ng sunud-sunod na pagtatantya, ay isang mathematical algorithm para sa paghahanap ng halaga ng hindi kilalang dami sa pamamagitan ng unti-unting pagpino nito. Ang kakanyahan ng pamamaraang ito ay, tulad ng ipinahihiwatig ng pangalan, unti-unting ipinahayag ang mga kasunod na mga mula sa paunang pagtatantya, nakakakuha sila ng higit at mas pinong mga resulta. Ang pamamaraang ito ay ginagamit upang mahanap ang halaga ng isang variable sa isang naibigay na function, gayundin upang malutas ang mga sistema ng mga equation, parehong linear at non-linear.

Isaalang-alang natin kung paano ipinatupad ang pamamaraang ito kapag nilulutas ang SLAE. Ang simpleng paraan ng pag-ulit ay may sumusunod na algorithm:

1. Pagpapatunay ng kundisyon ng convergence sa orihinal na matrix. Convergence theorem: kung ang orihinal na matrix ng system ay may dayagonal na dominasyon (ibig sabihin, sa bawat hilera, ang mga elemento ng pangunahing dayagonal ay dapat na mas malaki sa modulus kaysa sa kabuuan ng mga elemento ng pangalawang diagonal sa modulo), kung gayon ang paraan ng simple convergent ang mga pag-ulit.

2. Ang matrix ng orihinal na sistema ay hindi palaging may dayagonal na dominasyon. Sa ganitong mga kaso, maaaring ma-convert ang system. Ang mga equation na nakakatugon sa kondisyon ng convergence ay naiwang hindi nagagalaw, at sa mga hindi, bumubuo sila ng mga linear na kumbinasyon, i.e. multiply, ibawas, magdagdag ng mga equation sa bawat isa hanggang sa makuha ang nais na resulta.

Kung sa nagreresultang sistema ay may mga hindi maginhawang coefficient sa pangunahing dayagonal, kung gayon ang mga termino ng form na c i *x i ay idinagdag sa parehong bahagi ng naturang equation, ang mga palatandaan na dapat magkasabay sa mga palatandaan ng mga elemento ng dayagonal.

3. Pagbabago ng resultang sistema sa normal na anyo:

x - =β - +α*x -

Magagawa ito sa maraming paraan, halimbawa, tulad ng sumusunod: mula sa unang equation, ipahayag ang x 1 sa mga tuntunin ng iba pang hindi alam, mula sa pangalawa - x 2, mula sa pangatlo - x 3, atbp. Dito ginagamit namin ang mga formula:

α ij = -(a ij / a ii)

i = b i /a ii
Dapat mong tiyakin muli na ang resultang sistema ng normal na anyo ay nakakatugon sa kondisyon ng convergence:

∑ (j=1) |α ij |≤ 1, habang i= 1,2,...n

4. Nagsisimula kaming mag-aplay, sa katunayan, ang paraan ng sunud-sunod na pagtatantya mismo.

x (0) - paunang approximation, ipinapahayag namin sa pamamagitan nito x (1) , pagkatapos ay sa pamamagitan ng x (1) ipinapahayag namin ang x (2) . Ang pangkalahatang formula sa matrix form ay ganito:

x (n) = β - +α*x (n-1)

Kinakalkula namin hanggang sa maabot namin ang kinakailangang katumpakan:

max |x i (k)-x i (k+1) ≤ ε

Kaya, tingnan natin ang simpleng paraan ng pag-ulit sa pagsasanay. Halimbawa:
Lutasin ang SLAE:

4.5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 na may katumpakan ε=10 -3

Tingnan natin kung ang mga elemento ng dayagonal ay nangingibabaw sa modulo.

Nakikita namin na ang ikatlong equation lamang ang nakakatugon sa kondisyon ng convergence. Binabago namin ang una at pangalawang equation, idagdag ang pangalawa sa unang equation:

7.6x1+0.6x2+2.4x3=3

Ibawas ang una sa ikatlo:

2.7x1+4.2x2+1.2x3=2

Na-convert namin ang orihinal na sistema sa isang katumbas:

7.6x1+0.6x2+2.4x3=3
-2.7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

Ngayon, ibalik natin sa normal ang system:

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2

Sinusuri namin ang convergence ng umuulit na proseso:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , ibig sabihin. ang kundisyon ay natutugunan.

0,3947
Paunang hula x(0) = 0.4762
0,8511

Ang pagpapalit ng mga halagang ito sa normal na equation ng anyo, nakukuha namin ang mga sumusunod na halaga:

0,08835
x(1) = 0.486793
0,446639

Ang pagpapalit ng mga bagong halaga, makakakuha tayo ng:

0,215243
x(2) = 0.405396
0,558336

Ipinagpapatuloy namin ang mga kalkulasyon hanggang sa mas malapit kami sa mga halaga na nakakatugon sa ibinigay na kondisyon.

x(7) = 0.441091

Suriin natin ang kawastuhan ng mga nakuhang resulta:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0.1880+2.3*0.441-1.1x*0.544=0.9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Ang mga resulta na nakuha sa pamamagitan ng pagpapalit ng mga nahanap na halaga sa orihinal na mga equation ay ganap na nakakatugon sa mga kondisyon ng equation.

Tulad ng nakikita natin, ang simpleng paraan ng pag-ulit ay nagbibigay ng tumpak na mga resulta, gayunpaman, upang malutas ang equation na ito, kailangan naming gumugol ng maraming oras at gumawa ng masalimuot na mga kalkulasyon.