Metode rasio emas

Perhatikan susunan titik-titik yang simetris X 1 dan X 2 di segmen [ A; B], yang mana salah satunya menjadi titik uji pada segmen baru yang diperoleh setelah mengecualikan sebagian segmen asli. Penggunaan titik-titik tersebut memungkinkan, pada setiap iterasi metode eliminasi segmen, kecuali yang pertama, untuk membatasi diri pada penentuan hanya satu nilai. F(X), karena nilai lain sudah ditemukan di salah satu iterasi sebelumnya.

Mari kita perhatikan sebuah segmen terlebih dahulu dan, agar lebih pasti, asumsikan bahwa ketika segmen tersebut direduksi, sisi kanan segmen tersebut dihilangkan. Membiarkan X 2 = , maka suatu titik terletak simetris X 1 = 1- (Gbr. 2.2).

Beras. 2.2.

Titik percobaan X 1 segmen akan menuju ke trial point X 2 = 1- segmen baru. Ke titik X 2 = , dan X 2 = 1- kita membagi segmen-segmennya dan dalam perbandingan yang sama, persamaan atau harus dipenuhi, dari mana kita menemukan nilai positifnya... Jadi, X 1 = 1- = , .

Untuk segmen sembarang [ A; B] ekspresi untuk poin uji coba akan berbentuk

1. Poin X 1 dan X 2 mempunyai sifat sebagai berikut: masing-masing membagi segmen [ A; B] menjadi dua bagian yang tidak sama sehingga perbandingan panjang seluruh ruas dengan panjang bagian yang lebih besar sama dengan perbandingan panjang bagian yang lebih besar dan lebih kecil pada ruas tersebut. Poin dengan properti ini disebut poin rasio emas segmen [ A; B].

2. Pada setiap iterasi eliminasi segmen dengan titik uji, salah satunya berpindah ke segmen dan nilai berikutnya F(X) tidak boleh dihitung pada saat ini. Jika segmen baru menjadi [ A; X 2 ], maka titik uji segmen asal berpindah ke sana, menjadi titik uji kedua ( X 2 "= x 1) (Gbr. 2.2). Dalam hal transisi ke segmen [ X 1 ; B] titik uji segmen asal menjadi titik uji pertama segmen [ X 1 ; B].

3. Sangat mudah untuk memeriksanya X 1 =a+b-X 2, dan X 2 =a+b-X 1 . Oleh karena itu, pada setiap iterasi metode bagian emas, titik uji yang hilang dari suatu segmen baru dapat ditemukan dari titik uji yang diteruskan ke segmen tersebut dengan menggunakan penjumlahan dan pengurangan.

4. Pada akhir perhitungan menggunakan metode rasio emas sebagai nilai perkiraan X* Anda dapat mengambil bagian tengah dari segmen terakhir yang dihasilkan.

Pada setiap iterasi, segmen pencarian titik minimum berkurang dengan rasio yang sama, sehingga menghasilkan hasil P iterasi panjangnya menjadi. Jadi, keakuratannya N definisi titik X* setelah P iterasi ditemukan dari persamaan, dan syarat untuk mengakhiri pencarian suatu titik adalah X* pertidaksamaan n disajikan dengan akurat.

Contoh penyelesaian dengan menggunakan metode dikotomi dan bagian emas

Diberikan fungsi dimana d=2, e=1

Penting untuk menemukan nilai minimum pada segmen di mana, mis. pada segmen tersebut

Buatlah program yang akan memberikan jumlah iterasi dengan akurasi e=0,001

Selesaikan dengan dua metode: dikotomi dan rasio emas

Penyelesaian dengan metode dikotomi:

Sejak f1

Sejak f1

Solusi menggunakan metode rasio emas:

Sejak f1

Sejak f1

Sejak f1

Daftar program yang menerapkan metode dikotomi dan rasio emas disajikan pada Lampiran A

interval ketidakpastian, tetapi hanya n penghitungan fungsi yang dapat dilakukan. Bagaimana seharusnya n titik di mana fungsi dievaluasi dipilih? Pada pandangan pertama, tampak jelas bahwa seseorang tidak boleh mencari solusi untuk semua poin yang diperoleh dari percobaan. Sebaliknya, kita harus berusaha memastikan bahwa nilai fungsi yang diperoleh pada percobaan sebelumnya menentukan posisi titik-titik berikutnya. Memang, dengan mengetahui nilai suatu fungsi, kita memiliki informasi tentang fungsi itu sendiri dan posisi minimumnya dan menggunakan informasi ini untuk pencarian lebih lanjut.

Anggap saja ada interval ketidakpastian(x 1 ,x 3) dan nilai fungsi f(x 2) dalam interval ini diketahui (lihat Gambar 9.3). Jika fungsi tersebut dapat dievaluasi sekali saja pada titik x4, lalu di manakah titik x4 harus ditempatkan agar diperoleh nilai terkecil yang mungkin? interval ketidakpastian?

Beras. 9.3.

Misalkan x 2 – x 1 = L dan x 3 – x 2 = R, dan L > R, seperti ditunjukkan pada Gambar. 9.3, dan nilai-nilai ini akan tetap jika x 1, x 2 dan x 3 diketahui. Jika x 4 berada pada interval (x 1; x 2), maka:

1. jika f(x 4)< f(x 2) , то новым interval ketidakpastian akan menjadi (x 1 ,x 2) panjang x 2 – x 1 =L;
2. jika f(x 4)>f(x 2) maka baru interval ketidakpastian akan menjadi (x 4, x 3) panjang x 3 – x 4.

Karena tidak diketahui situasi mana yang akan terjadi, kita memilih x 4 sedemikian rupa untuk meminimalkan panjang terbesar x 3 - x 4 dan x 2 - x 1. Hal ini dapat dicapai dengan menyamakan panjang x 3 – x 4 dan x 2 – x 1, yaitu. menempatkan x 4 di dalam interval secara simetris relatif terhadap titik x 2 yang sudah berada di dalam interval. Posisi titik x 4 lainnya dapat mengakibatkan interval yang dihasilkan lebih besar dari L. Dengan menempatkan x 4 secara simetris terhadap x 2, kita tidak mengambil risiko apa pun. Jika ternyata perhitungan fungsi lainnya dapat dilakukan, maka prosedur yang dijelaskan harus diterapkan pada interval (x 1, x 2), yang di dalamnya sudah terdapat nilai fungsi yang dihitung pada titik x 4 , atau ke interval (x 4, x 3) yang didalamnya sudah terdapat nilai fungsi yang dihitung di titik x 2.

Oleh karena itu, strateginya sudah jelas sejak awal. Kita perlu menempatkan titik berikutnya di dalam interval ketidakpastian secara simetris relatif terhadap suatu titik yang sudah ada. Paradoksnya, untuk memahami bagaimana suatu perhitungan harus dimulai, kita perlu memahami bagaimana perhitungan tersebut harus diakhiri.

Pada perhitungan ke-n, titik ke-n harus ditempatkan secara simetris terhadap titik (n - 1). Posisi poin terakhir ini pada prinsipnya terserah kita. Untuk mendapatkan pengurangan interval terbesar pada tahap ini, interval sebelumnya harus dibagi dua. Maka titik x akan berimpit dengan titik x n-1. Namun, kami tidak menerima informasi baru apa pun. Biasanya, titik x n-1 dan x n berjarak cukup jauh untuk menentukan letak separuhnya, kiri atau kanan. interval ketidakpastian. Mereka ditempatkan pada jarak e/2 di kedua sisi tengah segmen L n-1; Anda dapat mengatur sendiri nilai e atau memilih nilai ini sama dengan jarak minimum yang mungkin antara dua titik.

Interval ketidakpastian akan memiliki panjang L n, oleh karena itu, L n-1 = 2L n - e (Gbr. 9.4, bagian bawah). Pada tahap sebelumnya, titik x n-1 dan x n-2 harus ditempatkan secara simetris dalam interval L n-2 pada jarak L n-2 dari ujung interval ini. Oleh karena itu, L n-2 = L n-1 + L n (Gbr. 9.4, bagian tengah).

Beras. 9.4.

Komentar. Jelas dari gambar bahwa pada tahap kedua dari belakang x n-2 tetap sebagai titik dalam.

Demikian pula L n-3 =L n-2 +L n-1 (Gbr. 9.4, bagian atas)

Secara umum, L j-1 =L j + L j+1 pada 1

Dengan demikian,

Jika kita mendefinisikan barisan bilangan Fibonacci sebagai berikut: F 0 =1, F 1 =l, dan F k =F k-1 +F k-2 untuk k = 2, 3,..., maka

Oleh karena itu, setelah melakukan n perhitungan fungsi, kita akan mengurangi fungsi awal interval ketidakpastian l/F n kali panjang awalnya (mengabaikan e), dan ini adalah hasil terbaik.

Setelah pencarian dimulai, mudah untuk melanjutkan menggunakan aturan simetri yang dijelaskan di atas. Oleh karena itu, perlu dicari posisi titik pertama yang terletak pada jarak L 2 dari salah satu ujung interval awal, dan tidak menjadi soal ujung mana, karena titik kedua ditempatkan menurut simetri. aturan pada jarak L 2 dari ujung kedua interval:

(2.4)

Setelah posisi titik pertama sudah ditemukan, angka Fibonacci tidak diperlukan lagi. Nilai e yang digunakan dapat ditentukan oleh pertimbangan praktis. Itu harus lebih kecil dari L 1 \F n+x , jika tidak kita akan membuang waktu menghitung fungsinya.

Jadi pencarian metode Fibonacci, dinamakan demikian karena kemunculannya saat mencari bilangan Fibonacci, merupakan prosedur berulang. Dalam proses pencarian interval (x1; x2) dengan titik x 2 yang terletak pada interval tersebut, selalu dipilih titik berikutnya x 2 sedemikian rupa sehingga x 3 – x 4 = x 2 – x 1 atau x 4 - x 1 = x 3 - x 2, mis. x 4 = x 1 - x 2 + x 3.

Jika f(x 2) = f 2 dan f(x 4) = f 4, maka empat kasus dapat dipertimbangkan (Gbr. 9.5).

Beras. 9.5.

Metode optimasi satu dimensi berikutnya disebut menggunakan metode "bagian emas"..

Tidak selalu mungkin untuk menentukan terlebih dahulu berapa kali suatu fungsi harus dievaluasi. DI DALAM metode Fibonacci ini perlu diketahui untuk menentukan L 2, yaitu. posisi titik awal (lihat persamaan 2.4).

Metode "bagian emas". hampir sama efektifnya dengan metode Fibonacci, namun tidak perlu mengetahui n, jumlah evaluasi fungsi, yang ditentukan di awal. Setelah perhitungan j selesai, berdasarkan pertimbangan yang sama seperti sebelumnya (lihat persamaan 2.1), kita tulis

Itu.

Jadi, dari mana. Kemudian

Perkenalan

Metode bagian emas mempunyai penerapan yang cukup luas di banyak bidang. Karena segala sesuatu di dunia ini mempunyai bentuk tertentu: benda, tumbuhan, hewan, manusia - semuanya. Apa sajakah bentuk-bentuk tersebut? Setiap keseluruhan harus dibagi menjadi beberapa bagian dengan ukuran berbeda. Bagian-bagian ini mempunyai hubungan satu sama lain dan dengan seluruh dunia, mereka mempunyai bentuk. Dan struktur bentuk apapun dibentuk menggunakan simetri dan rasio emas.

Metode rasio emas digunakan dalam fotografi dan lukisan. Bagi seorang fotografer, metode rasio emas adalah salah satu cara termudah untuk menonjolkan hal utama dalam sebuah gambar. Metode ini juga digunakan dalam desain web. Dalam seni lukis, contohnya adalah lukisan karya I.I. Shishkin "Hutan Pinus". Dalam lukisan terkenal karya I.I. Shishkin dengan jelas menunjukkan motif rasio emas. Pohon pinus yang terang benderang (berdiri di latar depan) membagi panjang gambar menurut rasio emas. Di sebelah kanan pohon pinus ada bukit kecil yang diterangi matahari. Ini membagi sisi kanan gambar secara horizontal sesuai dengan rasio emas. Di sebelah kiri pohon pinus utama terdapat banyak pohon pinus - jika diinginkan, Anda dapat terus membagi gambar sesuai dengan rasio emas lebih lanjut.

Metode bagian emas juga telah diterapkan dalam arsitektur. Hukum bagian emas digunakan untuk membangun gedung-gedung paling terkenal, seperti Parthenon (abad ke-5 SM), Katedral Notre Dame (Notre Dame de Paris). Contoh nyata dalam arsitektur Rusia adalah Katedral Smolny di St. Petersburg dan Katedral St. Basil, di mana, jika kita mengambil tinggi katedral sebagai satu kesatuan, maka proporsi dasar yang menentukan pembagian keseluruhan menjadi beberapa bagian membentuk a serangkaian rasio emas.

Pada dasarnya metode bagian emas digunakan dalam pemrograman. Ini adalah salah satu metode komputasi paling sederhana untuk memecahkan masalah optimasi.

Tujuan dari mata kuliah ini adalah untuk mempertimbangkan metode numerik untuk mencari fungsi ekstrem suatu variabel, yaitu metode bagian emas.

Berdasarkan tujuannya, tugas-tugas berikut perlu diselesaikan:

Pertimbangkan metode bagian emas dan algoritma implementasinya;

Pertimbangkan metode bilangan Fibonacci dan algoritma pelaksanaannya;

Tunjukkan penerapan metode bagian emas dalam pemrograman.

Metode rasio emas

Sejarah metode bagian emas

Masalah pemrograman linier adalah yang pertama mempelajari secara rinci masalah pencarian fungsi ekstrem dengan adanya kendala seperti pertidaksamaan. Pada tahun 1820, Fourier dan kemudian pada tahun 1947, Danzig mengusulkan metode pencacahan terarah dari simpul-simpul yang berdekatan ke arah peningkatan fungsi tujuan - metode simpleks, yang menjadi metode utama untuk menyelesaikan masalah program linier.

Kehadiran istilah “pemrograman” pada nama disiplin ilmu tersebut dijelaskan oleh fakta bahwa kajian pertama dan penerapan pertama masalah optimasi linier berada di bidang ilmu ekonomi, karena dalam bahasa Inggris kata “programming” berarti perencanaan, penyusunan. rencana atau program. Wajar jika terminologi tersebut mencerminkan hubungan erat yang terjalin antara rumusan masalah matematis dan interpretasi ekonominya (studi tentang program ekonomi optimal). Istilah "pemrograman linier" diciptakan oleh Danzig pada tahun 1949 untuk mempelajari masalah teoretis dan algoritmik yang terlibat dalam pengoptimalan fungsi linier dalam batasan linier.

Oleh karena itu, nama “pemrograman matematika” disebabkan oleh kenyataan bahwa tujuan pemecahan masalah adalah untuk memilih program tindakan yang optimal.

Identifikasi kelas masalah ekstrem yang ditentukan oleh fungsi linier pada himpunan yang ditentukan oleh batasan linier harus dimulai pada tahun 1930-an. Di antara orang pertama yang mempelajari masalah pemrograman linier dalam bentuk umum adalah: John von Neumann, seorang matematikawan dan fisikawan yang membuktikan teorema dasar tentang permainan matriks dan mempelajari model ekonomi yang menyandang namanya, dan Kantorovich, seorang akademisi Soviet dan penerima Hadiah Nobel. (1975), yang merumuskan sejumlah masalah program linier dan pada tahun 1939 mengusulkan metode penyelesaiannya (metode penyelesaian pengganda), yang sedikit berbeda dengan metode simpleks.

Pada tahun 1931, matematikawan Hongaria B. Egervary mempertimbangkan rumusan matematika dan memecahkan masalah pemrograman linier yang disebut “masalah pilihan”; metode penyelesaiannya disebut “metode Hongaria”.

Kantorovich bersama dengan M.K. Pada tahun 1949, Gavurin mengembangkan metode potensial yang digunakan dalam memecahkan masalah transportasi. Dalam karya-karya selanjutnya oleh Kantorovich, Nemchinov, V.V. Novozhilova, A.L. Lurie, A. Brudno, Aganbegyan, D.B. Yudina, mis. Holstein dan ahli matematika dan ekonom lainnya, baik teori matematika pemrograman linier dan nonlinier serta penerapan metodenya untuk mempelajari berbagai masalah ekonomi dikembangkan lebih lanjut.

Banyak karya ilmuwan asing yang dikhususkan untuk metode pemrograman linier. Pada tahun 1941 F.L. Hitchcock menimbulkan masalah transportasi. Metode utama untuk menyelesaikan masalah program linier, metode simpleks, diterbitkan pada tahun 1949 oleh Danzig. Metode pemrograman linier dan nonlinier dikembangkan lebih lanjut dalam karya Kuhn (Bahasa Inggris), A. Tucker (Bahasa Inggris), Gass (Saul. I. Gass), Charnes (A. Charnes), Beale (E.M.), dll.

Bersamaan dengan perkembangan pemrograman linier, banyak perhatian diberikan pada masalah pemrograman nonlinier yang fungsi tujuannya atau kendalanya, atau keduanya, adalah nonlinier. Pada tahun 1951, Kuhn dan Tucker menerbitkan sebuah makalah yang memberikan kondisi optimalitas yang diperlukan dan cukup untuk memecahkan masalah pemrograman nonlinier. Pekerjaan ini menjadi dasar untuk penelitian selanjutnya di bidang ini.

Sejak tahun 1955, banyak karya tentang pemrograman kuadrat telah diterbitkan (karya Beal, Barankin dan Dorfman R., Frank M. dan Wolfe P., Markowitz, dll.). Karya Dennis J.B., Rosen J.B. dan Zontendijk G. mengembangkan metode gradien untuk memecahkan masalah pemrograman nonlinier.

Saat ini, untuk penggunaan metode pemrograman matematika dan pemecahan masalah yang efektif pada komputer, bahasa pemodelan aljabar telah dikembangkan, yang perwakilannya adalah AMPL dan LINGO.

Konsep dan definisi metode bagian emas

Misalkan X=. Misalkan x1=1/T. Karena T2=T+1, maka 1-1/T=1/T2.

Jadi, perbandingan panjang seluruh ruas dengan panjang bagian yang lebih besar sama dengan perbandingan panjang bagian yang lebih besar dengan panjang bagian yang lebih kecil:

1/(1/T)=(1/T)/(1/T2)

Pembagian segmen dalam rasio ini disebut rasio emas.

Kita memilih titik x2 secara simetris ke titik x1 relatif terhadap titik tengah ruas X:x2=1/T2. Membandingkan nilai f(x1) dan f(x2), kita menemukan segmen lokalisasi minimum ( atau ). Sangat mudah untuk melihat bahwa titik yang terletak di dalam lokalisasi, tempat perhitungan dilakukan, membagi segmen tersebut kaitannya dengan rasio emas.

Algoritmanya ditentukan oleh kondisi yang sama pada metode Fibonacci, yaitu selisih pilihan titik x1. Pada setiap langkah, titik perhitungan berikutnya dipilih secara simetris terhadap titik tengah segmen ke titik perhitungan yang telah dilakukan yang terletak di dalam segmen tersebut.

Gambar 1 - Grafik posisi relatif dari 2 perhitungan pertama menggunakan metode bagian emas

Tabel 1 ? Posisi relatif titik-titik yang dihasilkan oleh algoritma

Jelasnya, dalam kasus X=, panjang segmen lokalisasi minimum setelah N perhitungan sama dengan (b-a)/(TN-1).

Dalam diagram blok ini kamu, z- titik pembagian segmen ,Dan kamu< z .

kamu = 0,618a + 0,382b

z = 0,382a + 0,618b

Fy = f(y) : Fz = f(z)

b-a< e b - a < e

z = y: Fz = Fy y = z: Fy = Fz

y = 0,618a + 0,382b z = 0,382a + 0,618b

Fy = f(y) Fz = f(z)

Keluaran x, f(x)

Contoh. Untuk memperkirakan hambatan jalan terhadap pergerakan kendaraan dengan kecepatan ay km/jam bisa menggunakan rumus empiris f(v) = 24 - 2/3*v + 1/30*v 2 (untuk jalan raya). Tentukan kecepatan pada saat hambatannya minimal.

Larutan.

1) Masalah ini dapat diselesaikan dengan mudah dengan menghitung turunannya:

, v = 10 km/jam.

2) Penyelesaian menggunakan metode “rasio emas”. Misalkan batas awal interval ketidakpastian sama dengan a = 5, b = 20.

Solusi untuk tahap pertama:

kamu = 0,618*5 + 0,382*20" 10,7: z = 0,382*5 + 0,618*20"14,3

Fy = 24 - 2*10,7/3 + 10,7 2 /30" 20,7: Fz = 24 - 2*14,3/3 + 14,3 2 /30" 21,3

Hasil perhitungan biasanya disajikan dalam bentuk tabel. Perhitungan dilakukan sesuai dengan diagram blok dengan error e = 1 km/jam.

Setelah lima langkah optimasi, nilai kecepatan yang diinginkan adalah v = (8.6+10.7)/2 = 9.65 km/jam. Setelah satu langkah lagi diperoleh hasil ini dengan error yang lebih kecil v = (9,4+10,7)/2 = 10,05 km/jam.

Optimalisasi fungsi beberapa variabel Minimal suatu fungsi beberapa variabel

Minimum fungsi terdiferensiasi dari banyak variabel u = f(x 1 , x 2 , ... , x n) dapat dicari dengan memeriksa nilainya pada titik kritis, yang ditentukan dari penyelesaian sistem persamaan diferensial

Perhatikan bahwa dalam kasus ini, titik kritis dapat berhubungan dengan titik ekstrim atau titik “sadel” (“titik minimax”). Titik-titik ini dipahami sebagai titik-titik yang fungsinya mempunyai nilai minimum pada beberapa arah, dan maksimum pada arah yang lain.

Contoh pernyataan masalah. Misalkan perlu untuk merancang sebuah wadah berbentuk paralelipipid persegi panjang dengan volume V=1 m 3, dan perlu menggunakan bahan sesedikit mungkin untuk pembuatannya.

Dengan ketebalan dinding yang konstan, kondisi ini berarti luas permukaan total wadah S harus minimal. Jika kita menyatakan panjang rusuk wadah dengan x 1 , x 2 dan x 3 , maka masalahnya akan direduksi menjadi meminimalkan fungsi:

S = 2 (x 1 x 2 + x 1 x 3 + x 2 x 3) .

Fungsi ini dalam hal ini adalah fungsi target, dan kondisi V = 1 m 3 merupakan batasan kesetaraan yang memungkinkan satu parameter dikecualikan:

.

Masalahnya direduksi menjadi meminimalkan fungsi dua variabel. Sebagai hasil penyelesaiannya, akan ditemukan nilai parameter optimasi x 1 dan x 2, lalu x 3. Pada contoh di atas, ternyata permasalahan optimasi tidak dibatasi, karena batasan persamaan digunakan untuk menghilangkan parameter x 3 .

Larutan. Setelah diferensiasi kita dapatkan

Dari sini didapat x 1 = x 2 = 1 m, x 3 = 1/(x 1 x 2) = 1 m. Jadi, bentuk wadah yang optimal dalam hal ini adalah kubus yang panjang rusuknya adalah 1 M.

Dengan pendekatan ini, kesulitan serius mungkin timbul ketika menyelesaikan sistem persamaan nonlinier.

Namun, tugas ini bisa jadi rumit. Misalnya, kita mensyaratkan bahwa wadah ini memiliki panjang minimal 2 m. Kondisi ini akan ditulis sebagai batasan pertidaksamaan pada salah satu parameter, misalnya x 1 ³ 2.

Jadi, kami mendapat masalah optimasi bersyarat berikut: minimalkan fungsi

memperhitungkan batasan pertidaksamaan x 1 ³ 2 dan mencari nilai optimal dari faktor x 2 , x 3 (x 2 ³0, x 3 ³0).

Representasi grafis dari fungsi dua variabel: pertimbangkan fungsinya

f(x 1 , x 2) = x 1 2 + x 2 2 .

Tampilkan garis dengan level yang sama untuk fungsi ini.

Berikan gambaran umum tentang tiga kemungkinan pilihan garis yang sejajar, tunjukkan fungsi “jurang”.

Dalam kasus umum, untuk mencari nilai minimum fungsi tujuan, Anda dapat memasukkan himpunan titik (simpul) diskrit dengan membagi interval perubahan parameter x 1 dan x 2 menjadi beberapa bagian dengan langkah h 1 dan h 2. Di node yang dihasilkan, Anda dapat menghitung nilai fungsi tujuan dan menemukan nilai terkecil di antara nilai tersebut. Namun, dalam permasalahan optimasi multidimensi, pendekatan ini memerlukan terlalu banyak komputasi.

Metode ini didasarkan pada konsep “bagian emas”, yang diperkenalkan oleh Leonardo da Vinci dan digunakan, khususnya, dalam konstruksi struktur arsitektur zaman kuno dan Renaisans.

Rasio emas suatu ruas adalah pembagiannya menjadi dua bagian yang tidak sama, sehingga perbandingan panjang seluruh ruas dengan panjang bagian yang lebih besar sama dengan perbandingan panjang bagian yang lebih besar dengan panjang bagian yang lebih kecil. bagian (Gbr. 1.3, kiri)

Rasio emas dilakukan oleh dua titik x1 dan x2, yang terletak simetris relatif terhadap tengah segmen (Gbr. 1.3, kanan). Sangat mudah untuk memeriksanya

Titik x1 melakukan rasio emas tidak hanya pada segmen, tetapi juga pada segmen, dan titik x2 melakukan rasio emas tidak hanya pada segmen, tetapi juga pada segmen. Benar-benar,

Dari (1.10) dan (1.11) kita memperoleh:

x1 = a + , x2 = a +. (1.12)

Rumus (1.12) merupakan rumus perhitungan utama metode bagian emas.

Dari (1.12) diperoleh x1 + x2 = a + b. Jika kita menyatakan r = , maka rumus (1.12) dapat ditulis ulang sebagai berikut:

x1 = b - r(b - a), x2 = a + r(b - a) (1.13)

Tata cara pembagian segmen sama dengan metode dikotomi dan Fibonacci. Nilai fungsi dihitung pada titik yang dipilih: f(x1) dan f(x2). Segmen lokalisasi baru ditentukan sebagai berikut:

jika f(x1) f(x2), maka a1 = a, b1 = x2;

jika f(x1) > f(x2), maka a1 = x1, b1 = b.

Seperti halnya pada metode Fibonacci, salah satu titik uji x1, x2 akan menjadi titik uji pada segmen lokalisasi baru. Oleh karena itu, pada setiap iterasi cukup menentukan satu nilai f(x saja), karena nilai lain sudah ditemukan pada iterasi sebelumnya.

Di akhir perhitungan, Anda dapat mengambil bagian tengah dari segmen terakhir yang diperoleh sebagai nilai perkiraan x*.

Setelah n iterasi, kesalahan memenuhi pertidaksamaan berikut:

Syarat penyelesaian perhitungan adalah terpenuhinya pertidaksamaan n<.

Algoritma 1.4 (Algoritma metode bagian emas).

Langkah 1. Masukkan data awal: a, b, . Tetapkan r = , n = .

Langkah 2. Tentukan x1 dan x2 menggunakan rumus (1.13).

Langkah 3. Hitung f(x1) dan f(x2).

Langkah 4. Periksa kriteria akhir perhitungan. Jika n<, перейти к шагу 5, иначе - к шагу 6.

Langkah 5. Buka segmen lokalisasi baru dan titik pengujian baru. Jika f(x1) f(x2), maka masukkan b = x2, x2 = x1, f(x2) = f(x1), x1 = b - r(b - a) dan hitunglah f(x1). Jika tidak, masukkan a = x1, x1 = x2, f(x1) = f(x2), x2 = a + r(b - a) dan hitung f(x2).

Tetapkan n = rn dan lanjutkan ke langkah 4.

Langkah 6. Masukkan x* . Hitung f * f(x*).

Implementasi dalam paket MathCAD 14

Mari kita cari nilai minimum dari fungsi f(x), x hingga

Hasilnya, diperoleh f(x*) = -3,749, x*=0,382 dengan akurasi 18 iterasi.