Semua orang pada dasarnya berjuang untuk mendapatkan pengetahuan. (Aristoteles. Metafisika)

Metode numerik: menyelesaikan persamaan nonlinier

Masalah penyelesaian persamaan selalu muncul dalam praktek, misalnya dalam ilmu ekonomi, ketika mengembangkan suatu usaha, Anda ingin mengetahui kapan keuntungan akan mencapai nilai tertentu, dalam kedokteran, ketika mempelajari efek obat, penting untuk mengetahui kapan konsentrasinya. suatu zat akan mencapai tingkat tertentu, dll.

Dalam permasalahan optimasi, seringkali diperlukan penentuan titik dimana turunan suatu fungsi menjadi 0, yang merupakan kondisi yang diperlukan lokal ekstrim.

Dalam statistik, saat membuat perkiraan menggunakan metode kuadrat terkecil atau kemungkinan maksimum, Anda juga harus menyelesaikan persamaan dan sistem persamaan nonlinier.

Jadi, seluruh kelas masalah muncul terkait dengan pencarian solusi nonlinier persamaan, misalnya persamaan atau persamaan, dsb.

Dalam kasus yang paling sederhana, kita mempunyai fungsi yang terdefinisi pada interval ( A, b ) dan mengambil nilai-nilai tertentu.

Setiap nilai X dari segmen ini kita bisa membandingkan jumlahnya, ini dia fungsional ketergantungan, konsep kunci dalam matematika.

Kita perlu mencari nilai yang disebut akar fungsi

Secara visual kita perlu menentukan titik potong grafik fungsidengan sumbu absis.

Metode membagi dua

Metode paling sederhana untuk mencari akar persamaan adalah metode membagi dua, atau pembelahan dua.

Metode ini bersifat intuitif dan setiap orang akan bertindak dengan cara yang sama ketika memecahkan suatu masalah.

Algoritmanya adalah sebagai berikut.

Misalkan kita menemukan dua titik dan , sehingga keduanya mempunyai berbeda tanda, maka di antara titik-titik tersebut paling sedikit terdapat satu akar fungsi.

Mari kita bagi segmennya menjadi dua dan masuk rata-rata titik.

Lalu juga , atau .

Mari kita tinggalkan separuh segmen yang nilai-nilai di ujungnya memiliki tanda berbeda. Sekarang kita membagi lagi segmen ini menjadi dua dan meninggalkan bagian itu pada batas-batas yang fungsinya memiliki tanda berbeda, dan seterusnya, untuk mencapai akurasi yang diperlukan.

Jelasnya, kami akan secara bertahap mempersempit area di mana akar dari fungsi tersebut berada, dan oleh karena itu, kami akan menentukannya dengan tingkat akurasi tertentu.

Perhatikan bahwa algoritma yang dijelaskan dapat diterapkan untuk fungsi kontinu apa pun.

Keuntungan dari metode halving adalah keandalan dan kesederhanaannya yang tinggi.

Kerugian dari metode ini adalah sebelum Anda mulai menggunakannya, Anda perlu menemukan dua titik di mana nilai fungsinya memiliki tanda yang berbeda. Jelas bahwa metode ini tidak dapat diterapkan pada akar-akar yang multiplisitasnya genap dan juga tidak dapat digeneralisasikan pada kasus akar-akar kompleks dan pada sistem persamaan.

Urutan konvergensi metode ini linier, pada setiap langkah akurasinya berlipat ganda; semakin banyak iterasi yang dilakukan, semakin akurat akar ditentukan.

Metode Newton: landasan teori

metode klasik Newton atau garis singgung adalah if yang merupakan perkiraan terhadap akar persamaan , maka perkiraan selanjutnya didefinisikan sebagai akar garis singgung fungsi yang ditarik di titik tersebut.

Persamaan tangen suatu fungsi di suatu titik berbentuk:

Dalam persamaan tangen kita masukkan dan .

Maka algoritma perhitungan sekuensial pada metode Newton adalah sebagai berikut:

Konvergensi metode tangen adalah kuadrat, orde konvergensinya adalah 2.

Dengan demikian, konvergensi metode tangen Newton sangat cepat.

Ingatlah fakta luar biasa ini!

Tanpa perubahan apa pun, metode ini digeneralisasikan ke kasus yang kompleks.

Jika akarnya adalah akar dengan multiplisitas kedua atau lebih tinggi, maka orde konvergensinya turun dan menjadi linier.

Latihan 1. Dengan menggunakan metode tangen, carilah penyelesaian persamaan pada segmen (0, 2).

Latihan 2. Dengan menggunakan metode tangen, carilah penyelesaian persamaan pada ruas (1, 3).

Kerugian dari metode Newton termasuk lokalitasnya, karena metode ini dijamin konvergen untuk perkiraan awal yang berubah-ubah hanya jika kondisinya terpenuhi di semua tempat. , sebaliknya, konvergensi hanya terjadi pada lingkungan akar tertentu.

Kerugian metode Newton adalah perlunya menghitung turunan pada setiap langkah.

Visualisasi metode Newton

Metode Newton (metode tangen) digunakan jika persamaan F(X) = 0 memiliki root dan kondisi berikut terpenuhi:

1) fungsi kamu= F(X) didefinisikan dan berkelanjutan di ;

2) F(A)· F(B) < 0 (fungsi mengambil nilai dari tanda yang berbeda di ujung segmen [ A; B]);

3) turunan F"(X) Dan F""(X) pertahankan tanda pada interval [ A; B] (yaitu fungsi F(X) baik bertambah atau berkurang pada ruas [ A; B], dengan tetap mempertahankan arah cembung);

Ide utama dari metode ini adalah sebagai berikut: pada segmen [ A; B] nomor tersebut dipilih X 0 , di mana F(X 0 ) memiliki tanda yang sama dengan F"" (X 0 ), yaitu kondisi terpenuhi F(X 0 )· F"" (X) > 0 . Dengan demikian, titik dengan absis dipilih X 0 , yang bersinggungan dengan kurva kamu= F(X) di segmen [ A; B] memotong sumbu Sapi. Per poin X 0 Pertama, akan lebih mudah untuk memilih salah satu ujung segmen.

Mari kita pertimbangkan metode Newton menggunakan contoh spesifik.

Mari kita diberi fungsi yang meningkat kamu = f(x) =x 2 -2, kontinu pada segmen (0;2), dan memiliki F"(x) = 2 X > 0 Dan F "" (x) = 2 > 0 .

Menggambar1 . f(x) =x 2 -2

Persamaan tangen dalam bentuk umum mempunyai gambaran sebagai berikut:

yy 0 = f" (x 0)·(x-x 0).

Dalam kasus kami: y-y 0 =2x 0 ·(x-x 0). Untuk titik x 0 kita pilih titiknya B 1 (b; f(b)) = (2,2). Gambarlah garis singgung fungsi tersebut kamu = f(x) di titik B 1, dan menunjukkan titik potong garis singgung dan sumbu Sapi dot x 1. Kita mendapatkan persamaan garis singgung pertama: y-2=2·2(x-2), y=4x-6.

Sapi: x 1 =

Menggambar2. Hasil iterasi pertama

kamu=f(x) Sapi melalui titik tersebut x 1, kami mengerti maksudnya B 2 =(1,5; 0,25). Gambarlah garis singgung fungsi tersebut lagi kamu = f(x) di titik B 2, dan menunjukkan titik potong garis singgung dan sumbu Sapi dot x 2.

Persamaan garis singgung kedua: kamu-0.25=2*1.5(X-1.5), kamu = 3 X - 4.25.

Titik potong garis singgung dan sumbu Sapi: x 2 =.

Menggambar3. Iterasi kedua metode Newton

Kemudian kita mencari titik potong fungsi tersebut kamu=f(x) dan ditarik tegak lurus terhadap sumbu Sapi melalui titik x 2 kita mendapatkan titik B 3 dan seterusnya.

Menggambar4. Langkah ketiga dari metode tangen

Perkiraan pertama dari akar ditentukan oleh rumus:

= 1.5.

Perkiraan kedua dari akar ditentukan oleh rumus:

Perkiraan ketiga dari akar ditentukan oleh rumus:

Dengan demikian , Saya Perkiraan akar ditentukan oleh rumus:

Perhitungan dilakukan sampai tempat desimal yang diperlukan dalam jawaban cocok, atau presisi e yang ditentukan tercapai - sampai pertidaksamaan terpenuhi | xi- xi-1 | < e.

Dalam kasus kita, mari kita bandingkan perkiraan yang diperoleh pada langkah ketiga dengan jawaban sebenarnya yang dihitung dengan kalkulator:

Gambar 5. Akar dari 2, dihitung dengan kalkulator

Seperti yang Anda lihat, pada langkah ketiga kami menerima kesalahan kurang dari 0,000002.

Dengan cara ini, Anda dapat menghitung nilai “akar kuadrat dari 2” dengan tingkat akurasi apa pun. Metode luar biasa ini ditemukan oleh Newton dan memungkinkan Anda menemukan akarnya dengan sangat baik persamaan kompleks.

Metode Newton: aplikasi dalam C++

Pada artikel ini, kami akan mengotomatiskan proses penghitungan akar persamaan dengan menulis aplikasi konsol di C++. Kami akan mengembangkannya dalam Visual C++ 2010 Express, ini adalah lingkungan pengembangan C++ yang gratis dan sangat nyaman.

Pertama, mari kita luncurkan Visual C++ 2010 Express. Jendela awal program akan muncul. Di pojok kiri, klik "Buat proyek".

Beras. 1. halaman rumah Visual C++ 2010 Ekspres

Pada menu yang muncul, pilih “Aplikasi Konsol Win32” dan masukkan nama aplikasi “Newton_Method”.

Beras. 2. Buat proyek

// Metode Newton.cpp: mendefinisikan titik masuk untuk aplikasi konsol

#sertakan "stdafx.h"

#termasuk

menggunakan namespace std;

float f(double x) //mengembalikan nilai fungsi f(x) = x^2-2

float df(float x) //mengembalikan nilai turunan

float d2f(float x) // nilai turunan kedua

ke dalam _tmain(ke dalam argc, _TCHAR* argv)

int exit = 0, i=0;//variabel untuk keluar dan loop

double x0,xn;//menghitung perkiraan untuk root

double a, b, eps; //batas segmen dan ketelitian yang dibutuhkan

cout<<"Please input \n=>";

cin>>a>>b; // masukkan batas segmen yang akan kita cari akarnya

cout<<"\nPlease input epsilon\n=>";

cin>>ep; // masukkan akurasi perhitungan yang diperlukan

if (a > b) // jika pengguna mencampuradukkan batas segmen, tukarkan

if (f(a)*f(b)>0) // jika tanda fungsi pada tepi segmen sama, maka tidak ada akar di sini

cout<<"\nError! No roots in this interval\n";

jika (f(a)*d2f(a)>0) x0 = a; // untuk memilih titik awal, centang f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // pertimbangkan perkiraan pertama

cout<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // akan terus menghitung hingga mencapai akurasi yang diperlukan

xn = x0-f(x0)/df(x0); // langsung rumus Newton

cout<<++i<<"-th iteration = "<

cout<<"\nRoot = "<

cout<<"\nExit?=>";

) sementara (keluar!=1); // sampai pengguna memasukkan exit = 1

Mari kita lihat cara kerjanya. Klik segitiga hijau di pojok kiri atas layar, atau tekan F5.

Jika terjadi kesalahan kompilasi “Kesalahan kesalahan LNK1123: kegagalan untuk mengkonversi ke COFF: file tidak valid atau rusak,” maka ini dapat disembuhkan dengan menginstal Service pack 1 pertama, atau dalam pengaturan proyek Properties -> Linker menonaktifkan tautan tambahan.

Beras. 4. Mengatasi kesalahan kompilasi proyek

Kami akan mencari akar fungsinya F(x) =x2-2.

Pertama, mari kita periksa kinerja aplikasi pada data input yang “salah”. Tidak ada akar pada segmen tersebut, program kita akan menampilkan pesan kesalahan.

Kami sekarang memiliki jendela aplikasi:

Beras. 5. Memasukkan data masukan

Mari kita perkenalkan batas segmen 3 dan 5, dan akurasinya adalah 0,05. Program ini, seperti yang diharapkan, menghasilkan pesan kesalahan bahwa tidak ada akar pada segmen ini.

Beras. 6. Kesalahan “Tidak ada akar pada segmen ini!”

Kami belum akan pergi, jadi bagaimana dengan pesan “Keluar?” masukkan "0".

Sekarang mari kita periksa aplikasi menggunakan data input yang benar. Mari kita masuk ke segmen dan akurasi 0,0001.

Beras. 7. Perhitungan root dengan akurasi yang dibutuhkan

Seperti yang bisa kita lihat, akurasi yang dibutuhkan sudah tercapai pada iterasi ke-4.

Untuk keluar dari aplikasi, masukkan “Keluar?” => 1.

Metode garis potong

Untuk menghindari penghitungan turunan, metode Newton dapat disederhanakan dengan mengganti turunan dengan perkiraan yang dihitung dari dua poin sebelumnya:

Proses berulangnya terlihat seperti:

Ini adalah proses berulang dua langkah karena menggunakan dua langkah sebelumnya untuk menemukan perkiraan berikutnya.

Urutan konvergensi metode garis potong lebih rendah dibandingkan metode tangen dan sama untuk akar tunggal.

Besaran yang luar biasa ini disebut rasio emas:

Mari kita verifikasi ini, dengan asumsi demi kenyamanan bahwa .

Jadi, hingga tingkat yang lebih tinggi hingga sangat kecil

Dengan membuang suku sisanya, kita memperoleh relasi perulangan, yang penyelesaiannya secara alami dicari dalam bentuk .

Setelah substitusi kita memiliki: dan

Oleh karena itu, untuk konvergensi, konvergensi harus positif.

Karena pengetahuan tentang turunan tidak diperlukan, dengan jumlah perhitungan yang sama pada metode garis potong (walaupun orde konvergensinya lebih rendah), akurasi yang lebih besar dapat dicapai dibandingkan dengan metode tangen.

Perhatikan bahwa di dekat akar Anda harus membaginya dengan angka kecil, dan ini menyebabkan hilangnya akurasi (terutama dalam kasus banyak akar), oleh karena itu, setelah memilih angka yang relatif kecil, lakukan perhitungan sebelum melakukan dan lanjutkan hingga modulus selisih antara perkiraan tetangga berkurang.

Segera setelah pertumbuhan dimulai, penghitungan dihentikan dan iterasi terakhir tidak digunakan.

Prosedur untuk menentukan akhir iterasi ini disebut teknik Garvika.

metode parabola

Mari kita pertimbangkan metode tiga langkah yang perkiraannya ditentukan oleh tiga poin sebelumnya, dan.

Untuk melakukan ini, kita mengganti, mirip dengan metode garis potong, fungsi tersebut dengan parabola interpolasi yang melalui titik , dan .

Dalam bentuk Newton terlihat seperti:

Suatu titik didefinisikan sebagai salah satu akar polinomial yang nilai absolutnya lebih dekat dengan titik tersebut.

Orde konvergensi metode parabola lebih tinggi dibandingkan metode garis potong, namun lebih rendah dibandingkan metode Newton.

Perbedaan penting dari metode yang telah dibahas sebelumnya adalah kenyataan bahwa meskipun real untuk real dan perkiraan awal dipilih sebagai real, metode parabola dapat menghasilkan akar kompleks dari permasalahan awal.

Metode ini sangat mudah untuk mencari akar polinomial derajat tinggi.

Metode iterasi sederhana

Masalah pencarian solusi persamaan dapat dirumuskan sebagai masalah pencarian akar: , atau sebagai masalah pencarian titik tetap.

Membiarkan dan - kompresi: (khususnya, fakta bahwa - kompresi, seperti yang mudah dilihat, berarti demikian).

Menurut teorema Banach, terdapat titik tetap yang unik

Ini dapat ditemukan sebagai batas dari prosedur berulang yang sederhana

di mana perkiraan awal adalah titik sembarang dalam interval.

Jika fungsinya terdiferensiasi, maka kriteria kompresi yang tepat adalah bilangan . Memang benar, menurut teorema Lagrange

Jadi, jika turunannya kurang dari satu maka merupakan kompresi.

Kondisi ini penting, karena jika misalnya pada , maka tidak ada titik tetap, meskipun turunannya sama dengan nol. Kecepatan konvergensi bergantung pada nilai . Semakin kecil , semakin cepat konvergensinya.

Misalkan akar persamaan f(x)=0 dipisahkan pada ruas , dengan turunan pertama dan kedua f’(x) dan f""(x) kontinu dan bertanda konstan untuk xÎ.

Biarkan pada beberapa langkah penyempurnaan akar, perkiraan berikutnya ke akar x n diperoleh (dipilih) . Maka misalkan perkiraan selanjutnya diperoleh dengan menggunakan koreksi h n , mengarah ke nilai pasti dari akar

x = xn + hn. (1.2.3-6)

Perhitungan h n nilai kecil, kita nyatakan f(х n + h n) dalam bentuk deret Taylor, membatasi diri pada suku linier

f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)

Mengingat f(x) = f(x n + h n) = 0, kita peroleh f(x n) + h n f ’(x n) » 0.

Oleh karena itu h n » - f(x n)/ f’(x n). Mari kita substitusikan nilainya h n di (1.2.3-6) dan sebagai ganti nilai pasti dari root X kita mendapatkan perkiraan lain

Rumus (1.2.3-8) memungkinkan kita memperoleh barisan perkiraan x 1, x 2, x 3 ..., yang, dalam kondisi tertentu, konvergen ke nilai eksak akar X, itu adalah

Interpretasi geometris metode Newton adalah sebagai berikut
(Gbr.1.2.3-6). Mari kita ambil ujung kanan segmen b sebagai perkiraan awal x 0 dan buatlah garis singgung di titik yang bersesuaian B 0 pada grafik fungsi y = f(x). Titik perpotongan garis singgung dengan sumbu x diambil sebagai pendekatan baru yang lebih akurat x 1. Mengulangi prosedur ini berkali-kali memungkinkan kita memperoleh barisan perkiraan x 0, x 1, x 2 , . . ., yang cenderung pada nilai eksak dari akarnya X.

Rumus perhitungan metode Newton (1.2.3-8) dapat diperoleh dari konstruksi geometri. Jadi pada segitiga siku-siku x 0 B 0 x 1 kaki
x 0 x 1 = x 0 V 0 /tga. Mengingat titik B 0 berada pada grafik fungsi f(x), dan sisi miringnya dibentuk oleh garis singgung grafik f(x) di titik B 0, kita peroleh

(1.2.3-9)

(1.2.3-10)

Rumus ini bertepatan dengan (1.2.3-8) untuk pendekatan ke-n.

Dari Gambar 1.2.3-6 jelas bahwa pemilihan titik a sebagai perkiraan awal dapat mengarah pada fakta bahwa perkiraan berikutnya x 1 akan berada di luar segmen di mana akar dipisahkan X. Dalam hal ini, konvergensi proses tidak dijamin. Dalam kasus umum, pemilihan aproksimasi awal dilakukan sesuai dengan aturan berikut: aproksimasi awal harus diambil sebagai titik x 0 , di mana f(x 0)×f''(x 0)>0 , yaitu tanda-tanda fungsi dan turunan keduanya cocok.

Syarat konvergensi metode Newton dirumuskan dalam teorema berikut.

Jika akar persamaan dipisahkan menjadi segmen, Dan f'(x 0) dan f''(x) berbeda dari nol dan mempertahankan tandanya ketika xО, lalu jika kita memilih titik tersebut sebagai perkiraan awal x 0 О , Apa f(x 0).f¢¢(x 0)>0 , maka akar persamaannya f(x)=0 dapat dihitung dengan tingkat akurasi apa pun.

Estimasi kesalahan metode Newton ditentukan oleh ekspresi berikut:

(1.2.3-11)

dimana nilai terkecilnya pada

Nilai tertinggi pada

Proses perhitungan berhenti jika ,

di mana akurasi yang ditentukan.

Selain itu, ekspresi berikut dapat berfungsi sebagai syarat untuk mencapai akurasi tertentu saat menyempurnakan akar menggunakan metode Newton:

Diagram algoritma metode Newton ditunjukkan pada Gambar. 1.2.3-7.

Sisi kiri persamaan asli f(x) dan turunannya f’(x) dalam algoritma dirancang sebagai modul perangkat lunak terpisah.

Beras. 1.2.3-7. Diagram algoritma metode Newton

Contoh 1.2.3-3 Sempurnakan akar-akar persamaan x-ln(x+2) = 0 dengan menggunakan metode Newton, dengan syarat akar-akar persamaan tersebut dipisahkan pada ruas-ruas x 1 О[-1.9;-1.1] dan x 2 tentang [-0,9;2 ].

Turunan pertama f’(x) = 1 – 1/(x+2) mempertahankan tandanya pada setiap segmen:

f'(x)<0 при хÎ [-1.9; -1.1],

f'(x)>0 pada xО [-0.9; 2].

Turunan kedua f"(x) = 1/(x+2) 2 > 0 untuk sembarang x.

Dengan demikian, kondisi konvergensi terpenuhi. Karena f""(x)>0 pada seluruh rentang nilai yang diizinkan, maka untuk memperjelas akar dari perkiraan awal x 1 pilih x 0 = -1.9 (karena f(-1.9)×f”(-1.9)>0). Kami memperoleh urutan perkiraan:

Melanjutkan perhitungan, kita memperoleh urutan empat perkiraan pertama berikut: -1.9; –1.8552, -1.8421; -1.8414 . Nilai fungsi f(x) di titik x=-1,8414 sama dengan f(-1,8414)=-0,00003 .

Untuk memperjelas akar x 2 О[-0.9;2] kita memilih 0 =2 (f(2)×f”(2)>0) sebagai perkiraan awal. Berdasarkan x 0 = 2, kita memperoleh barisan aproksimasi: 2.0;1.1817; 1,1462; 1.1461. Nilai fungsi f(x) di titik x=1,1461 sama dengan f(1,1461)= -0,00006.

Metode Newton memiliki tingkat konvergensi yang tinggi, namun pada setiap langkahnya memerlukan penghitungan tidak hanya nilai fungsi, tetapi juga turunannya.

Metode akord

Interpretasi geometris dari metode akord adalah sebagai berikut
(Gbr.1.2.3-8).

Mari kita menggambar ruas garis yang melalui titik A dan B. Perkiraan selanjutnya x 1 adalah absis titik potong tali busur dengan sumbu 0x. Mari kita buat persamaan ruas garis lurus:

Mari kita atur y=0 dan temukan nilainya x=x 1 (perkiraan berikutnya):

Mari kita ulangi proses perhitungan untuk mendapatkan perkiraan akar berikutnya - x 2 :

Dalam kasus kami (Gbr. 1.2.11) dan akan terlihat seperti apa rumus perhitungan metode chord tersebut

Rumus ini berlaku jika titik b diambil sebagai titik tetap, dan titik a bertindak sebagai perkiraan awal.

Mari kita pertimbangkan kasus lain (Gbr. 1.2.3-9), kapan .

Persamaan garis lurus untuk kasus ini mempunyai bentuk

Perkiraan selanjutnya x 1 pada y = 0

Maka rumus berulang metode chord untuk kasus ini berbentuk

Perlu dicatat bahwa titik tetap dalam metode tali busur dipilih menjadi ujung segmen yang kondisi f (x)∙f¢¢ (x)>0 terpenuhi.

Jadi, jika titik a diambil sebagai titik tetap , maka x 0 = b bertindak sebagai perkiraan awal, dan sebaliknya.

Kondisi cukup yang menjamin perhitungan akar persamaan f(x) = 0 menggunakan rumus tali busur akan sama dengan metode tangen (metode Newton), hanya saja sebagai pengganti pendekatan awal, yang dipilih adalah titik tetap. Metode akord merupakan modifikasi dari metode Newton. Bedanya, aproksimasi selanjutnya pada metode Newton adalah titik potong garis singgung dengan sumbu 0X, dan pada metode tali busur - titik potong tali busur dengan sumbu 0X - aproksimasinya menyatu ke akar dari sisi yang berbeda. .

Estimasi kesalahan untuk metode chord diberikan oleh ekspresi

(1.2.3-15)

Kondisi untuk mengakhiri proses iterasi menggunakan metode chord

(1.2.3-16)

Dalam kasus M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Contoh 1.2.3-4. Perjelas akar persamaan e x – 3x = 0 yang dipisahkan pada ruas dengan ketelitian 10 -4.

Mari kita periksa kondisi konvergensinya:

Akibatnya, a=0 harus dipilih sebagai titik tetap, dan x 0 =1 harus diambil sebagai perkiraan awal, karena f(0)=1>0 dan f(0)*f"(0)>0.

Saat berjuang di sekolah dengan menyelesaikan persamaan dalam pelajaran matematika, banyak siswa sering kali yakin bahwa mereka membuang-buang waktu dengan sia-sia, namun keterampilan seperti itu akan berguna dalam kehidupan tidak hanya bagi mereka yang memutuskan untuk mengikuti jejak Descartes, Euler atau Lobachevsky.

Dalam praktiknya, misalnya di bidang kedokteran atau ekonomi, seringkali terdapat situasi di mana seorang spesialis perlu mengetahui kapan konsentrasinya zat aktif suatu obat tertentu akan mencapai tingkat yang dibutuhkan dalam darah pasien, atau perlu untuk menghitung waktu yang dibutuhkan agar bisnis tertentu menjadi menguntungkan.

Paling sering kita berbicara tentang penyelesaian persamaan nonlinier berbagai jenis. Metode numerik memungkinkan hal ini dilakukan secepat mungkin, terutama dengan menggunakan komputer. Mereka telah dipelajari dengan baik dan telah lama terbukti keefektifannya. Ini termasuk metode tangen Newton, yang menjadi pokok bahasan artikel ini.

Rumusan masalah

Dalam hal ini terdapat fungsi g yang terdefinisi pada segmen (a, b) dan mengambil nilai tertentu pada segmen tersebut, yaitu setiap x milik (a, b) dapat diasosiasikan dengan bilangan tertentu g (X).

Semua akar persamaan harus ditentukan dari interval antara titik a dan b (termasuk ujung-ujungnya), yang fungsinya disetel ke nol. Jelasnya, ini adalah titik potong y = g(x) dengan OX.

Dalam beberapa kasus, akan lebih mudah untuk mengganti g(x)=0 dengan yang serupa, seperti g 1 (x) = g 2 (x). Dalam hal ini, absis (nilai x) titik potong grafik g 1 (x) dan g 2 (x) bertindak sebagai akar.

Penyelesaian persamaan nonlinier juga penting untuk masalah optimasi yang syarat ekstrem lokalnya adalah turunan fungsi berubah menjadi 0. Dengan kata lain, permasalahan tersebut dapat direduksi menjadi mencari akar-akar persamaan p(x) = 0, dimana p(x) identik dengan g"(x).

Metode solusi

Untuk beberapa jenis persamaan nonlinier, seperti persamaan kuadrat atau persamaan trigonometri sederhana, akar dapat dicari dengan cara yang cukup sederhana. Secara khusus, setiap anak sekolah mengetahui rumus-rumus yang dapat digunakan untuk dengan mudah mencari nilai argumen titik-titik di mana trinomial kuadrat hilang.

Metode ekstraksi akar persamaan nonlinier biasanya dibagi menjadi analitis (langsung) dan iteratif. Dalam kasus pertama, solusi yang diinginkan berbentuk rumus, yang dengannya, dalam sejumlah operasi aritmatika tertentu, seseorang dapat menemukan nilai akar yang diinginkan. Metode serupa telah dikembangkan untuk eksponensial, trigonometri, logaritma dan sederhana persamaan aljabar. Selebihnya, Anda harus menggunakan metode numerik khusus. Mereka mudah diimplementasikan menggunakan komputer, yang memungkinkan Anda menemukan akarnya dengan akurasi yang diperlukan.

Ini termasuk yang disebut metode numerik Garis singgung Yang terakhir ini dikemukakan oleh ilmuwan besar Isaac Newton pada akhir abad ke-17. Pada abad-abad berikutnya, metode ini ditingkatkan berkali-kali.

Lokalisasi

Metode numerik untuk menyelesaikan persamaan kompleks yang tidak memiliki solusi analitis biasanya dilakukan dalam 2 tahap. Pertama, Anda perlu melokalisasinya. Operasi ini terdiri dari menemukan segmen pada OX yang memiliki satu akar persamaan yang diselesaikan.

Mari kita pertimbangkan segmennya. Jika g(x) tidak mempunyai diskontinuitas dan mempunyai nilai yang berbeda tanda pada titik-titik ujungnya, maka antara a dan b atau di dalamnya paling sedikit terdapat 1 akar persamaan g(x) = 0. Agar g(x) dapat agar unik, g(x) harus tidak monotonik. Seperti diketahui, sifat ini akan dimiliki asalkan tanda g’(x) konstan.

Dengan kata lain, jika g(x) tidak mempunyai diskontinuitas dan bertambah atau berkurang secara monoton, dan nilainya pada titik-titik akhir tidak mempunyai tanda yang sama, maka terdapat 1 dan hanya 1 akar dari g(x).

Namun perlu Anda ketahui bahwa kriteria ini tidak berlaku untuk akar-akar persamaan yang merupakan kelipatan.

Menyelesaikan persamaan dengan membagi dua

Sebelum mempertimbangkan garis singgung numerik yang lebih kompleks dan variasinya, ada baiknya Anda mengenal lebih dekat dengan cara yang sederhana mengidentifikasi akar. Ini disebut dikotomi dan mengacu pada cara intuitif untuk menemukan akar, berdasarkan teorema bahwa jika untuk g(x), kontinu, kondisi tanda yang berbeda terpenuhi, maka pada segmen yang dipertimbangkan setidaknya terdapat 1 akar g( x) = 0.

Untuk menemukannya, Anda perlu membagi segmen menjadi dua dan menetapkan titik tengahnya sebagai x 2. Maka ada dua pilihan yang mungkin: g(x 0) * g(x 2) atau g(x 2) * g(x 1) sama dengan atau kurang dari 0. Kita pilih salah satu pertidaksamaan ini yang benar. Kami mengulangi prosedur yang dijelaskan di atas hingga panjangnya menjadi kurang dari nilai tertentu yang telah dipilih sebelumnya yang menentukan keakuratan penentuan akar persamaan pada .

Keuntungan dari metode ini mencakup keandalan dan kesederhanaannya, namun kelemahannya adalah perlunya mengidentifikasi titik-titik di mana g(x) memiliki tanda yang berbeda, sehingga tidak dapat digunakan untuk akar-akar multiplisitas genap. Selain itu, ini tidak menggeneralisasi kasus sistem persamaan atau jika kita berbicara tentang akar kompleks.

Contoh 1

Mari kita selesaikan persamaan g(x) = 2x 5 + x - 1 = 0. Agar tidak menghabiskan waktu lama mencari segmen yang sesuai, kita buat grafiknya menggunakan, misalnya, program Excel yang terkenal . Kami melihat bahwa lebih baik mengambil nilai dari interval sebagai segmen untuk melokalisasi root. Kita dapat yakin bahwa setidaknya ada satu akar persamaan yang diperlukan pada persamaan tersebut.

g"(x) = 10x 4 + 1, yaitu fungsi naik monoton, jadi hanya ada 1 akar pada ruas yang dipilih.

Kami mengganti titik akhir ke dalam persamaan. Kami memiliki 0 dan 1 masing-masing. Pada langkah pertama kita ambil poin 0.5 sebagai solusinya. Maka g(0,5) = -0,4375. Ini berarti segmen berikutnya yang akan dibelah dua adalah . Miliknya titik tengah- 0,75. Di dalamnya, nilai fungsinya adalah 0,226. Kita ambil contoh ruas dan bagian tengahnya yang terletak di titik 0,625. Kita hitung nilai g(x) menjadi 0,625. Itu sama dengan -0,11, yaitu negatif. Berdasarkan hasil ini, kami memilih segmen tersebut. Kita mendapatkan x = 0,6875. Maka g(x) = -0,00532. Jika keakuratan penyelesaiannya adalah 0,01, maka kita dapat mengasumsikan bahwa hasil yang diinginkan adalah 0,6875.

Landasan teori

Metode pencarian akar menggunakan metode tangen Newton ini populer karena konvergensinya yang sangat cepat.

Hal ini didasarkan pada fakta yang terbukti bahwa jika x n merupakan aproksimasi terhadap akar f(x) = 0, sehingga f" C 1, maka aproksimasi berikutnya berada pada titik dimana persamaan garis singgung f(x) adalah nol, mis.

Gantikan x = x n+1 dan setel y ke nol.

Maka garis singgungnya terlihat seperti ini:

Contoh 2

Mari kita coba menggunakan metode tangen klasik Newton dan mencari solusi untuk beberapa persamaan nonlinier yang sulit atau tidak mungkin ditemukan secara analitis.

Misalkan perlu untuk mengidentifikasi akar-akar x 3 + 4x - 3 = 0 dengan ketelitian tertentu, misalnya 0,001. Sebagaimana diketahui, grafik suatu fungsi yang berbentuk polinomial berderajat ganjil harus memotong sumbu OX paling sedikit satu kali, yaitu tidak ada keraguan tentang keberadaan akar.

Sebelum menyelesaikan contoh kita menggunakan metode tangen, kita buat grafik f(x) = x 3 + 4x - 3 titik. Ini sangat mudah dilakukan, misalnya menggunakan prosesor spreadsheet Excel. Dari grafik yang dihasilkan terlihat tidak berpotongan dengan sumbu OX dan fungsi y = x 3 + 4x - 3 bertambah secara monoton. Kita dapat yakin bahwa persamaan x 3 + 4x - 3 = 0 mempunyai solusi dan unik.

Algoritma

Setiap penyelesaian persamaan dengan metode tangen dimulai dengan perhitungan f"(x). Kita mempunyai:

Maka turunan keduanya adalah x * 6.

Dengan menggunakan ekspresi berikut, kita dapat menulis rumus untuk mengidentifikasi akar-akar persamaan menggunakan metode tangen dalam bentuk:

Selanjutnya, Anda perlu memilih perkiraan awal, yaitu memutuskan titik mana yang akan dianggap sebagai titik awal (volume x 0) untuk proses iteratif. Kami mempertimbangkan ujung segmen. Kita akan menggunakan syarat yang benar bahwa fungsi dan turunan ke-2 di x 0 bertanda berbeda. Seperti yang bisa kita lihat, ketika mensubstitusi x 0 = 0 rusak, tetapi x 0 = 1 cukup cocok.

maka jika kita tertarik untuk menyelesaikan metode tangen dengan ketelitian e, maka nilai x n dianggap memenuhi syarat soal, dengan ketentuan pertidaksamaan |f(x n) / f’(x n)|< e.

Pada langkah singgung pertama kita mempunyai:

x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
karena syaratnya tidak terpenuhi, kita lanjutkan;
kita mendapatkan nilai baru untuk x 2 yaitu sebesar 0,674;
kita perhatikan perbandingan nilai fungsi terhadap turunannya di x 2 kurang dari 0,0063, kita hentikan prosesnya.

Metode Tangen di Excel

Anda dapat menyelesaikan contoh sebelumnya dengan lebih mudah dan cepat jika Anda tidak melakukan perhitungan secara manual (pada kalkulator), tetapi menggunakan kemampuan prosesor spreadsheet dari Microsoft.

Untuk melakukan ini, Anda perlu membuat halaman baru di Excel dan mengisi selnya dengan rumus berikut:

di C7 kita menulis “= GELAR (B7;3) + 4 * B7 - 3”;
di D7 kita masukkan “= 4 + 3 * GELAR (B7;2)”;
di E7 kita menulis “= (GELAR (B7;3)- 3 + 4 * B7) / (3* GELAR (B7;2) + 4)”;
di D7 kita memasukkan ekspresi “=B7 - E7”;
pada B8 kita masukkan rumus kondisi “=IF(E7< 0,001;"Завершение итераций"; D7)».

Dalam soal tertentu, tulisan “Menyelesaikan iterasi” akan muncul di sel B10, dan untuk menyelesaikan soal tersebut Anda perlu mengambil nomor yang tertulis di sel yang terletak satu baris di atas. Anda juga dapat memilih kolom terpisah yang "dapat diregangkan" dengan memasukkan kondisi rumus di sana, yang menurutnya hasilnya akan ditulis di sana jika konten dalam satu atau beberapa sel kolom B berbentuk "Penyelesaian iterasi".

Implementasi dalam Pascal

Mari kita coba mencari solusi persamaan nonlinier y = x 4 - 4 - 2 * x menggunakan metode tangen dalam Pascal.

Kami menggunakan fungsi bantu yang akan membantu melakukan perhitungan perkiraan f"(x) = (f(x + delta) - f(x)) / delta. Sebagai syarat untuk menyelesaikan proses iteratif, kami memilih pemenuhan pertidaksamaan |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Program ini terkenal karena tidak memerlukan penghitungan turunan secara manual.

Metode akord

Mari pertimbangkan cara lain untuk mengidentifikasi akar-akar persamaan nonlinier. Proses iterasi terdiri dari fakta bahwa sebagai perkiraan berturut-turut ke akar yang diinginkan untuk f(x) = 0, diambil nilai titik potong tali busur dengan absis titik akhir a dan b dengan OX, dilambangkan dengan x 1, ..., x n. Kita punya:

Untuk titik potong tali busur dengan sumbu OX, persamaannya ditulis sebagai:

Misalkan turunan keduanya positif untuk x £ (kasus sebaliknya akan direduksi menjadi kasus yang dibahas jika kita menulis f(x) = 0). Dalam hal ini grafik y = f(x) berbentuk kurva, bagian bawahnya cembung dan terletak di bawah tali busur. AB. Ada 2 kasus: ketika fungsi mempunyai nilai positif di titik a atau negatif di titik b.

Dalam kasus pertama, kita memilih ujung a sebagai ujung tetap, dan mengambil titik b sebagai x 0. Kemudian aproksimasi yang berurutan menurut rumus yang disajikan di atas membentuk suatu barisan yang menurun secara monoton.

Dalam kasus kedua, ujung b ditetapkan di x 0 = a. Nilai x yang diperoleh pada setiap langkah iterasi membentuk barisan yang meningkat secara monoton.

Dengan demikian, kita dapat menyatakan bahwa:

dalam metode tali busur, ujung segmen yang tetap adalah ujung yang tanda fungsi dan turunannya yang kedua tidak berhimpitan;
perkiraan untuk akar x - x m - terletak pada sisi di mana f(x) mempunyai tanda yang tidak bertepatan dengan tanda f"" (x).

Iterasi dapat dilanjutkan hingga kondisi kedekatan akar terpenuhi pada langkah iterasi ini dan langkah iterasi sebelumnya modulo abs(x m - x m - 1)< e.

Metode yang dimodifikasi

Metode gabungan tali busur dan garis singgung memungkinkan Anda menentukan akar persamaan dengan mendekatinya dari sisi yang berbeda. Nilai ini, di mana grafik f(x) berpotongan OX, memungkinkan Anda menyempurnakan solusi lebih cepat daripada menggunakan masing-masing metode secara terpisah.

Misalkan kita perlu mencari akar-akar dari f(x)=0, jika akar-akar tersebut ada di . Anda dapat menerapkan salah satu metode yang dijelaskan di atas. Namun, lebih baik mencoba kombinasi keduanya, yang akan meningkatkan akurasi root secara signifikan.

Kami mempertimbangkan kasus ini dengan perkiraan awal yang sesuai dengan kondisi bahwa turunan pertama dan kedua memiliki tanda yang berbeda pada titik x tertentu.

Dalam kondisi seperti itu, menyelesaikan persamaan nonlinier dengan metode tangen memungkinkan seseorang menemukan akar yang berlebih jika x 0 =b, dan metode yang menggunakan tali busur dengan ujung tetap b akan menghasilkan pencarian akar perkiraan yang memiliki kekurangan.

Rumus yang digunakan:

Sekarang akar x yang diperlukan harus dicari dalam interval. Pada langkah selanjutnya, Anda perlu menerapkan metode gabungan pada segmen ini. Dengan cara ini, kita memperoleh rumus dalam bentuk:

Jika turunan pertama dan kedua mempunyai tanda yang berbeda, maka dengan alasan yang sama, untuk memperjelas akar kita memperoleh rumus berulang berikut:

Kondisi yang digunakan adalah estimasi ketimpangan| b n +1 - an +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Jika pertidaksamaan di atas benar, maka sebagai akar persamaan nonlinier pada suatu segmen tertentu, ambil titik yang tepat berada di tengah-tengah antara solusi yang ditemukan pada langkah iterasi tertentu.

Metode gabungan ini mudah diimplementasikan di lingkungan TURBO PASCAL. Jika memang ingin, Anda bisa mencoba melakukan semua perhitungan menggunakan metode tabel di Excel.

Dalam kasus terakhir, beberapa kolom dialokasikan untuk menyelesaikan masalah menggunakan tali busur dan secara terpisah untuk metode yang diusulkan oleh Isaac Newton.

Dalam hal ini, setiap baris digunakan untuk mencatat perhitungan pada langkah iterasi tertentu menggunakan dua metode. Kemudian, di sisi kiri area solusi, sebuah kolom disorot pada halaman kerja aktif, di mana hasil penghitungan modul selisih nilai langkah iteratif berikutnya untuk masing-masing metode dimasukkan. Satu lagi dapat digunakan untuk memasukkan hasil perhitungan berdasarkan rumus menghitung konstruk logika “IF”, digunakan untuk mengetahui benar atau tidaknya suatu kondisi.

Sekarang Anda tahu cara menyelesaikan persamaan kompleks. Metode tangen, seperti yang telah Anda lihat, diimplementasikan dengan cukup sederhana, baik di Pascal maupun Excel. Oleh karena itu, Anda selalu dapat menentukan akar-akar persamaan yang sulit atau tidak mungkin diselesaikan dengan menggunakan rumus.

Sama seperti perkiraan. Istilah P. kadang-kadang digunakan dalam arti mendekatkan suatu benda (misalnya P. awal) ... Ensiklopedia Matematika

metode Newton- Metode Newton, Algoritma Newton (juga dikenal sebagai metode tangen) adalah metode numerik berulang untuk mencari akar (nol) dari suatu fungsi tertentu. Metode ini pertama kali dikemukakan oleh fisikawan, matematikawan, dan astronom Inggris Isaac Newton... ... Wikipedia

Salah satu metode singgung

Metode Gauss-Newton- Metode Newton (juga dikenal sebagai metode tangen) adalah metode numerik berulang untuk mencari akar (nol) suatu fungsi tertentu. Metode ini pertama kali dikemukakan oleh fisikawan, matematikawan, dan astronom Inggris Isaac Newton (1643 1727), dengan nama ... ... Wikipedia

metode Newton-Raphson- Metode Newton (juga dikenal sebagai metode tangen) adalah metode numerik berulang untuk mencari akar (nol) suatu fungsi tertentu. Metode ini pertama kali dikemukakan oleh fisikawan, matematikawan, dan astronom Inggris Isaac Newton (1643 1727), dengan nama ... ... Wikipedia

Metode singgung- Metode Newton (juga dikenal sebagai metode tangen) adalah metode numerik berulang untuk mencari akar (nol) suatu fungsi tertentu. Metode ini pertama kali dikemukakan oleh fisikawan, matematikawan, dan astronom Inggris Isaac Newton (1643 1727), dengan nama ... ... Wikipedia

Metode tangen (metode Newton)- Metode Newton (juga dikenal sebagai metode tangen) adalah metode numerik berulang untuk mencari akar (nol) suatu fungsi tertentu. Metode ini pertama kali dikemukakan oleh fisikawan, matematikawan, dan astronom Inggris Isaac Newton (1643 1727), dengan nama ... ... Wikipedia

Solusi numerik persamaan- dan sistemnya terdiri dari perkiraan penentuan akar atau akar suatu persamaan atau sistem persamaan dan digunakan dalam kasus di mana tidak mungkin atau sangat melelahkan untuk menghitung nilai pastinya. Daftar Isi 1 Pernyataan Masalah 2 Metode numerik ... Wikipedia

Metode perkiraan berturut-turut- metode untuk memecahkan masalah matematika menggunakan urutan perkiraan yang konvergen ke solusi dan dibangun secara rekursif (yaitu, setiap perkiraan baru dihitung berdasarkan perkiraan sebelumnya; perkiraan awal dipilih di ... ... Ensiklopedia Besar Soviet

Dalam masalah meminimalkan suatu fungsi, pemilihan pendekatan awal yang berhasil sangatlah penting.Tentu saja, tidak mungkin menghasilkan aturan umum yang memuaskan untuk semua kasus, yaitu untuk semua kemungkinan fungsi nonlinier. Setiap kali Anda harus mencari solusi Anda sendiri. Di bawah ini kami mengusulkan serangkaian metode untuk menemukan perkiraan awal yang kasar, yang dalam praktiknya dapat berfungsi sebagai titik awal untuk mencari perkiraan yang memuaskan dalam suatu masalah tertentu.

9.6.1. Pencarian jaringan. Metode ini sangat efektif dengan sejumlah kecil parameter nonlinier aktual. Seringkali fungsi dirancang sedemikian rupa sehingga ketika nilai beberapa parameter (yang kita sebut nonlinier) tetap, parameter lainnya menjadi linier.

Setelah kemudian menentukan batas bawah dan atas untuk parameter nonlinier, dengan langkah tertentu dimungkinkan untuk menghitung opsi pada kisi nilai yang dihasilkan dari parameter nonlinier itu sendiri dan mengidentifikasi regresi linier yang mengarah ke jumlah minimum kotak .

Sebagai contoh, perhatikan fungsinya

Di sini parameter nonlinier sebenarnya adalah . Katakanlah diketahui bahwa . Misalkan h adalah langkah untuk parameternya. Mari kita menghitung regresi linier

di mana kita menemukan jumlah minimum kuadrat untuk masing-masing kuadrat. Yang terkecil sesuai dengan perkiraan awal yang optimal. Pada prinsipnya, langkah yang menjadi sandaran “densitas” grid dapat bervariasi, sehingga dengan menurunkan nilai h, nilai parameter dapat ditemukan dengan akurat.

9.6.2. Transformasi model.

Terkadang, dengan beberapa transformasi, model dapat direduksi menjadi linier atau jumlah parameter nonlinier aktual dapat dikurangi (lihat bagian 6.2.3). Mari kita tunjukkan bagaimana hal ini dapat dicapai dengan menggunakan contoh kurva logistik

Melakukan transformasi terbalik pada persamaan regresi yang sesuai, kita memperoleh

Dengan menyatakannya, kita sampai pada fungsi baru, yang jumlah parameter liniernya meningkat dari satu menjadi dua. Estimasi parameter pada model baru dapat diketahui, misalnya dengan menggunakan metode sebelumnya.

Di sini patut dikemukakan pernyataan berikut tentang transformasi model regresi. Perlu diingat bahwa kesalahan yang merupakan penjumlahan pada persamaan awal, secara umum, tidak lagi menjadi penjumlahan setelah transformasi.

Dengan menggunakan ekspansi deret Taylor dan menyatakan transformasi dengan, kita peroleh dengan mengabaikan suku-suku keteraturan

Oleh karena itu

Persamaan terakhir dapat dijadikan dasar untuk menganalisis masalah dengan model yang ditransformasikan.

9.6.3. Membagi sampel menjadi sub-sampel.

Untuk mencari perkiraan awal, Anda dapat membagi seluruh sampel menjadi subsampel (dengan volume yang kira-kira sama), di mana adalah jumlah parameter yang tidak diketahui. Untuk setiap subsampel, kita mencari rata-rata atas y dan atas X, yang masing-masing dilambangkan dengan m. Mari kita selesaikan sistem persamaan nonlinier untuk

Solusi untuk sistem ini adalah perkiraan awal parameternya. Tentunya, agar metode ini “berhasil”, sistem persamaan nonlinier ini perlu diselesaikan dengan cukup mudah, misalnya secara analitis.

9.6.4. Ekspansi deret Taylor pada variabel bebas.

Dasar dari minimalisasi berulang jumlah kuadrat adalah perluasan fungsi regresi dalam deret Taylor ke suku linier dalam parameter. Untuk mencari perkiraan awal yang kasar, prosedur perkiraan regresi dengan memperluasnya menjadi deret Taylor pada variabel bebas terkadang berguna. Untuk mempermudah, kita asumsikan bahwa ini adalah satu dimensi. Biarlah nilai rata-ratanya, lalu kira-kira

Kita menyatakan , sehingga kita sampai pada model linier

Misalkan estimasi kuadrat terkecil dari parameter regresi linier ini. Sebagai perkiraan awal, kita akan mengambil solusi sistem persamaan nonlinier terhadap