Oleh karena itu berikut ini | (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Jadi, agar metode konvergen, cukup bahwa x [ a , b ] | (x) | 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

Algoritma umum dari aproksimasi berurutan[ | ]

Seperti yang diterapkan pada kasus umum persamaan operator, metode ini disebut metode aproksimasi berurutan atau metode iterasi sederhana. Namun, persamaan dapat ditransformasikan ke pemetaan kontraksi , yang memiliki akar yang sama, dengan cara yang berbeda. Hal ini memunculkan sejumlah metode tertentu yang memiliki tingkat konvergensi linier dan lebih tinggi.

Seperti yang diterapkan pada SLAU[ | ]

Pertimbangkan sistemnya:

( 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.)

Untuk itu, perhitungan iteratif akan terlihat seperti ini:

(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)\ akhir (array))\kanan)^(i+1)=\kiri((\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 )\kiri((\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))

Metode akan konvergen pada laju linier jika a 11 + 1 … a 1 n 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}

Bilah vertikal ganda berarti beberapa norma matriks.

Penyelesaian persamaan f(x)=0 dengan metode Newton, pendekatan awal: x 1 =a.

Metode Newton (metode tangen)[ | ]

Kasus satu dimensi[ | ]

Mengoptimalkan transformasi persamaan asli f (x) = 0 (\gaya tampilan f(x)=0) ke dalam pemetaan kontraksi x = (x) (\displaystyle x=\varphi (x)) memungkinkan Anda untuk mendapatkan metode dengan tingkat konvergensi kuadratik.

Agar pemetaan menjadi paling efisien, perlu pada titik iterasi berikutnya x (\gaya tampilan x^(*)) dilakukan (x ) = 0 (\displaystyle \varphi "(x^(*))=0). Kami akan mencari solusi untuk persamaan ini dalam bentuk (x) = x + (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), kemudian:

Mari kita gunakan apa f (x) = 0 (\gaya tampilan f(x)=0), dan kita mendapatkan rumus akhir untuk (x) (\displaystyle \alpha (x)):

Dengan mengingat hal ini, fungsi kontraksi akan berbentuk:

Kemudian algoritma untuk menemukan solusi numerik untuk persamaan f (x) = 0 (\gaya tampilan f(x)=0) direduksi menjadi prosedur perhitungan berulang:

Metode Iteratif

Metode iteratif mengasumsikan implementasi dari tiga tahap berikut: konstruksi proses iteratif yang konvergen ke solusi eksak untuk menghitung aproksimasi berurutan (yaitu, membangun urutan vektor yang konvergen ke solusi eksak ; penentuan kriteria konvergensi dari proses ini, yang memungkinkan penentuan momen pencapaian akurasi yang diperlukan; studi tentang tingkat konvergensi dan optimasi proses iteratif untuk mengurangi jumlah operasi yang diperlukan untuk mencapai akurasi yang dibutuhkan.

Metode iteratif memungkinkan untuk mendapatkan solusi dengan akurasi yang telah ditentukan, jika konvergensi metode terbukti. Metode iteratif tidak memberikan solusi yang benar-benar eksak, karena dicapai sebagai limit dari barisan vektor. Metode langsung umumnya memberikan solusi yang tepat, tetapi karena kesalahan pembulatan yang terjadi di semua komputer, itu tidak dapat dicapai, dan sebuah prioritas bahkan sulit untuk menilai seberapa jauh solusi ini berbeda dari solusi yang tepat. Sehubungan dengan hal di atas, terkadang metode iteratif memungkinkan untuk mendapatkan solusi dengan akurasi yang lebih tinggi daripada solusi langsung.

Pertimbangkan beberapa metode iteratif untuk menyelesaikan persamaan linier.

Metode iterasi sederhana

Dalam metode iterasi sederhana, sistem (2.1) persamaan aljabar linier kapak = b direduksi menjadi sistem ekivalen dengan bentuk

Solusi dari sistem (2.9) dan, akibatnya, solusi dari sistem asli (2.1) dicari sebagai limit dari barisan vektor untuk :

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

di mana adalah pendekatan awal untuk vektor solusi.

Kondisi cukup untuk konvergensi metode iterasi sederhana ditentukan oleh teorema berikut.

TEOREMA 1. Jika ada norma matriks yang konsisten dengan norma vektor yang dipertimbangkan lebih kecil dari satu (), maka barisan dalam metode iterasi sederhana konvergen ke solusi eksak sistem (2.9) dengan laju tidak kurang dari laju dari deret geometri dengan penyebut untuk setiap aproksimasi awal .

BUKTI. Untuk membuktikan teorema, kami memperkenalkan kesalahan . Dengan mengurangkan persamaan (2.10) dari relasi, kita peroleh . Melewati norma, kita punya

Perhatikan bahwa pertidaksamaan dari ekspresi sebelumnya adalah kondisi konsistensi untuk norma matriks dan vektor. Jika sebuah , maka untuk setiap vektor kesalahan awal (atau sebaliknya, untuk setiap vektor awal ), tingkat kesalahan cenderung nol tidak lebih lambat dari deret geometri dengan penyebut .

Jika kita memilih norma sebagai norma matriks atau kemudian untuk menyelesaikan pertanyaan tentang konvergensi metode iterasi sederhana, seseorang dapat menggunakan akibat wajar dari Teorema 1: metode iterasi sederhana konvergen jika salah satu kondisi berikut dipenuhi untuk matriks:

, saya = 1,2, …, n,

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

Cara paling sederhana dan paling umum untuk membawa sistem kapak = b ke bentuk (2.9), nyaman untuk iterasi, adalah pemilihan elemen diagonal, dengan masing-masing saya-itu persamaan diselesaikan sehubungan dengan saya-itu tidak dikenal:

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

dan metode iterasi sederhana dapat ditulis sebagai

Matriks tersebut kemudian memiliki bentuk

.

Elemen matriks ini dapat ditulis sebagai di mana adalah simbol Kronecker. Dalam hal ini, kondisi cukup untuk konvergensi metode iterasi sederhana dapat dirumuskan sebagai kondisi dominasi elemen diagonal dari matriks. TETAPI, yang mengikuti dari (2.11) dan notasi matriks , yaitu

i = 1, 2, …, n.

Kami menekankan sekali lagi bahwa bentuk yang dipertimbangkan dari kondisi untuk konvergensi metode iterasi hanya cukup. Eksekusi mereka menjamin konvergensi metode, tetapi kegagalan mereka dalam kasus umum tidak berarti bahwa metode iterasi sederhana menyimpang. Syarat perlu dan cukup untuk konvergensi metode iterasi sederhana adalah syarat bahwa bagian bilangan bulat (dimana adalah nilai eigen modulo maksimum dari matriks TETAPI); kondisi ini jarang digunakan dalam praktik komputasi.

Mari kita beralih ke pertanyaan memperkirakan kesalahan solusi. Yang menarik adalah dua hubungan untuk memperkirakan kesalahan solusi: yang pertama menghubungkan norma kesalahan dengan norma perbedaan dua pendekatan yang berurutan dan dapat digunakan untuk memperkirakan kesalahan hanya dalam proses perhitungan; yang kedua menghubungkan norma kesalahan dengan norma vektor aproksimasi awal dan vektor suku bebas dalam sistem (2.9). Hubungan yang diperlukan diberikan oleh dua teorema berikut.

TEOREMA 2. Jika ada norma matriks yang konsisten dengan norma vektor yang dipertimbangkan X

. (2.13)

BUKTI. Mari kita kurangi persamaan (2.10) dari persamaan:

Mengurangi dari kedua bagian nilai aproksimasi , kami mengubah rasio ini menjadi bentuk

Melewati norma, kita mendapatkan

Karena, dengan hipotesis teorema,

Menggunakan hubungan dari mana ia mengikuti bahwa akhirnya kita mendapatkan:

TEOREMA 3. Jika suatu norma adalah matriks yang konsisten dengan norma yang dipertimbangkan dari vektor X, kurang dari satu (), maka perkiraan kesalahan berikut terjadi:

Mari kita membuat dua komentar. Pertama, relasi (2.13) dapat ditulis sebagai

yang memungkinkan untuk memperoleh perkiraan kesalahan berdasarkan hasil dari dua iterasi pertama. Pertama, ketika menggunakan metode iterasi, kadang-kadang dianjurkan untuk menggunakan norma selisih dua pendekatan yang berurutan sebagai penduga kesalahan perhitungan. Ini mengikuti dari korelasi untuk kesalahan bahwa ini tidak benar dalam kasus umum. Jika normanya mendekati satu, maka koefisien di bisa sangat besar.

Kesalahan dari iterasi berturut-turut terkait dengan relasi

itu. kesalahan berubah secara linier pada suatu langkah. Metode dikatakan memiliki konvergensi linier atau konvergensi orde pertama. Namun, jumlah iterasi yang diperlukan untuk mencapai akurasi yang diperlukan bergantung pada nilai dan aproksimasi awal .

Jadi, dengan menggunakan metode iterasi sederhana sebagai contoh, tiga tahap metode iteratif ditunjukkan: konstruksi urutan vektor yang dihasilkan oleh rumus (1.10); penentuan kondisi konvergensi menurut Teorema 1 dan pendugaan laju konvergensi menggunakan Teorema 2 dan 3.

Metode Seidel

Metode iterasi sederhana tidak menggunakan kemungkinan yang tampak jelas untuk meningkatkan konvergensi proses iteratif - pengenalan langsung komponen vektor yang baru dihitung ke dalam perhitungan. Kemungkinan ini digunakan dalam metode Seidel iteratif. Proses iteratif untuk sistem (2.9) dilakukan dalam hal ini sesuai dengan relasi

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

atau untuk sistem (1.1)

Tanpa masuk ke detail, kami mencatat bahwa metode iterasi Seidel sering memang mengarah pada konvergensi yang lebih cepat daripada metode iterasi sederhana. Namun, ada kasus di mana metode iterasi Seidel konvergen lebih lambat daripada metode iterasi sederhana, dan bahkan kasus di mana metode iterasi sederhana konvergen tetapi metode iterasi Seidel menyimpang.

Perhatikan bahwa metode Seidel konvergen, jika matriks TETAPI pasti positif dan simetris.

Mari kita tunjukkan bahwa metode iterasi Seidel setara dengan beberapa metode iterasi sederhana dengan matriks dan vektor yang dibangun secara khusus dalam relasi (2.10). Untuk melakukan ini, kami menulis sistem (2.14) dalam bentuk Matriks (E-H) adalah matriks segitiga bawah dengan elemen diagonal sama dengan satu. Oleh karena itu, determinan matriks ini bukan nol (sama dengan satu) dan memiliki matriks invers . Kemudian

Membandingkan hubungan ini dengan solusi (2.10), kita dapat menyimpulkan bahwa metode iterasi Seidel memang setara dengan metode iterasi sederhana dalam arti bahwa, untuk menetapkan kondisi dan kriteria konvergensi untuk metode iterasi Seidel, seseorang dapat menggunakan teorema yang diberikan untuk metode iterasi sederhana, jika kita menetapkan Proses iteratif untuk sistem (2.12) juga dapat ditulis dalam bentuk yang lebih umum, yaitu:

Biarkan sistem persamaan aljabar n dengan n tidak diketahui diberikan:

Algoritma metode iterasi sederhana:

Perhatikan bahwa di sini dan selanjutnya, subskrip menunjukkan komponen yang sesuai dari vektor yang tidak diketahui, dan superskrip menunjukkan nomor iterasi (perkiraan).

Kemudian proses matematis siklik terbentuk, setiap siklus yang mewakili satu iterasi. Sebagai hasil dari setiap iterasi, diperoleh nilai baru dari vektor yang tidak diketahui. Untuk mengatur proses iteratif, kami menulis sistem (1) dalam bentuk di atas. Dalam hal ini, istilah pada diagonal utama dinormalisasi dan tetap di kiri tanda sama dengan, sedangkan sisanya dipindahkan ke sisi kanan. Sistem persamaan tereduksi seperti:

perhatikan itu tidak akan pernah tercapai, namun, dengan setiap iterasi berikutnya, vektor yang tidak diketahui semakin dekat dan mendekati solusi eksak.

12. Rumus iterasi utama yang digunakan dalam metode iterasi sederhana untuk menyelesaikan persamaan nonlinier:

13. Kriteria penghentian proses iterasi pada metode iterasi sederhana untuk penyelesaian persamaan nonlinier:

Proses iterasi berakhir jika untuk setiap komponen ke-i dari vektor yang tidak diketahui kondisi untuk mencapai akurasi terpenuhi.
perhatikan itu solusi eksak dalam metode iterasi sederhana tidak akan pernah tercapai, namun, dengan setiap iterasi berikutnya, vektor yang tidak diketahui semakin dekat dan mendekati solusi eksak

14. Kriteria pemilihan fungsi bantu F(x) untuk segmen iterasi dari interval :

Saat melakukan tes matematika untuk menyelesaikan metode iterasi sederhana, kondisi konvergensi harus diperiksa terlebih dahulu. Untuk konvergensi metode, perlu dan cukup bahwa dalam matriks A nilai absolut semua elemen diagonal lebih besar daripada jumlah modul semua elemen lain di baris yang sesuai:

Kerugian dari metode iteratif Ini adalah kondisi konvergensi yang cukup ketat, yang jauh dari terpenuhi untuk semua sistem persamaan.

Jika kondisi konvergensi terpenuhi, maka pada tahap selanjutnya perlu ditetapkan aproksimasi awal dari vektor yang tidak diketahui, yang biasanya vektor nol:

15. Metode Gauss yang digunakan untuk menyelesaikan sistem persamaan linear menyediakan:

Metode ini didasarkan pada transformasi matriks ke bentuk segitiga. Hal ini dicapai dengan eliminasi berurutan dari yang tidak diketahui dari persamaan sistem.

Metode iterasi sederhana, juga disebut metode aproksimasi berturut-turut, adalah algoritma matematika untuk menemukan nilai besaran yang tidak diketahui dengan memperbaikinya secara bertahap. Inti dari metode ini adalah, seperti namanya, secara bertahap mengekspresikan yang berikutnya dari perkiraan awal, mereka mendapatkan hasil yang lebih halus. Metode ini digunakan untuk mencari nilai suatu variabel dalam suatu fungsi tertentu, serta untuk menyelesaikan sistem persamaan, baik linier maupun nonlinier.

Mari kita pertimbangkan bagaimana metode ini diterapkan saat menyelesaikan SLAE. Metode iterasi sederhana memiliki algoritma berikut:

1. Verifikasi kondisi konvergensi dalam matriks asli. Teorema konvergensi: jika matriks asli sistem memiliki dominasi diagonal (yaitu, di setiap baris, elemen-elemen diagonal utama harus lebih besar dalam modulus daripada jumlah elemen diagonal sekunder dalam modulo), maka metode sederhana iterasi adalah konvergen.

2. Matriks sistem asli tidak selalu memiliki dominasi diagonal. Dalam kasus seperti itu, sistem dapat dimodifikasi. Persamaan yang memenuhi kondisi konvergensi dibiarkan tidak tersentuh, dan dengan yang tidak, mereka membentuk kombinasi linier, yaitu. mengalikan, mengurangi, menambahkan persamaan satu sama lain sampai diperoleh hasil yang diinginkan.

Jika dalam sistem yang dihasilkan ada koefisien yang tidak nyaman pada diagonal utama, maka istilah bentuk c i *x i ditambahkan ke kedua bagian dari persamaan tersebut, yang tanda-tandanya harus bertepatan dengan tanda-tanda elemen diagonal.

3. Transformasi sistem yang dihasilkan ke bentuk normal:

x - =β - +α*x -

Ini dapat dilakukan dengan banyak cara, misalnya, sebagai berikut: dari persamaan pertama, nyatakan x 1 dalam hal yang tidak diketahui lainnya, dari yang kedua - x 2, dari yang ketiga - x 3, dll. Di sini kita menggunakan rumus:

ij = -(a ij / a ii)

i = b i /a ii
Anda harus kembali memastikan bahwa sistem bentuk normal yang dihasilkan memenuhi kondisi konvergensi:

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

4. Kami mulai menerapkan, pada kenyataannya, metode aproksimasi berurutan itu sendiri.

x (0) - pendekatan awal, kami menyatakan melalui x (1) , kemudian melalui x (1) kami mengungkapkan x (2) . Rumus umum dalam bentuk matriks terlihat seperti ini:

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

Kami menghitung sampai kami mencapai akurasi yang diperlukan:

maks |x i (k)-x i (k+1)

Jadi, mari kita lihat metode iterasi sederhana dalam praktiknya. Contoh:
Selesaikan SLAE:

4.5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 dengan akurasi =10 -3

Mari kita lihat apakah elemen diagonal mendominasi modulo.

Kita melihat bahwa hanya persamaan ketiga yang memenuhi kondisi konvergensi. Kami mengubah persamaan pertama dan kedua, menambahkan yang kedua ke persamaan pertama:

7.6x1+0.6x2+2.4x3=3

Kurangi yang pertama dari yang ketiga:

2.7x1+4.2x2+1.2x3=2

Kami telah mengubah sistem asli menjadi sistem yang setara:

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

Sekarang mari kita kembalikan sistem ke normal:

x1=0,3947-0,0789x2-0,3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0,8511-0,383x1-0,5319x2

Kami memeriksa konvergensi dari proses iteratif:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 1 , yaitu. kondisi terpenuhi.

0,3947
Tebakan awal x(0) = 0,4762
0,8511

Mensubstitusi nilai-nilai ini ke dalam persamaan bentuk normal, kami memperoleh nilai-nilai berikut:

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

Mengganti nilai baru, kita mendapatkan:

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

Kami melanjutkan perhitungan sampai kami mendekati nilai yang memenuhi kondisi yang diberikan.

x(7) = 0,441091

Mari kita periksa kebenaran hasil yang diperoleh:

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

Hasil yang diperoleh dengan mensubstitusi nilai yang ditemukan ke dalam persamaan asli sepenuhnya memenuhi kondisi persamaan.

Seperti yang dapat kita lihat, metode iterasi sederhana memberikan hasil yang cukup akurat, namun untuk menyelesaikan persamaan ini, kami harus menghabiskan banyak waktu dan melakukan perhitungan yang rumit.