Kaedah lulus ialah pengubahsuaian kaedah Gauss untuk kes khas sistem jarang - sistem persamaan dengan matriks tridiagonal. Sistem sedemikian diperoleh dengan memodelkan beberapa masalah kejuruteraan, dan juga bila penyelesaian berangka masalah nilai sempadan untuk persamaan pembezaan.

Mari kita tulis sistem persamaan dalam bentuk

Pada pepenjuru utama matriks sistem ini terdapat unsur-unsur b 1, b 2, …, bn, di atasnya adalah unsur-unsur Dengan1, s2,... , sn-1 di bawahnya adalah unsur-unsur A 2, A 3,... , naik(biasanya semua pekali bi tidak sama dengan sifar). Baki unsur matriks adalah sama dengan sifar.

Kaedah lulus terdiri daripada dua peringkat - lari lurus(bersamaan dengan gerakan ke hadapan kaedah Gaussian) dan sapuan terbalik(bersamaan dengan songsangan kaedah Gaussian). Sapuan terus terdiri daripada mengira pekali sapuan Ai,Bi, dengan bantuan yang setiap x tidak diketahui i dinyatakan melalui zi+1 :

Daripada persamaan pertama sistem (2.13) kita dapati

Sebaliknya, mengikut formula (2.14) Menyamakan pekali dalam kedua-dua ungkapan untuk X 1, kita dapat

(2.15)

Mari kita gantikan ke dalam persamaan kedua sistem (2.13). X 1 ekspresinya melalui X 2mengikut formula (2.14):

Jom luahkan dari sini X 2 melalui X 3:

Pekali berjalan dikira sama untuk sebarang nombor i:

(2.16)

Sapuan ke belakang terdiri daripada pengiraan yang tidak diketahui secara berurutan xi. Mula-mula anda perlu mencari HP Untuk melakukan ini, kami menggunakan ungkapan (2.14) untuk i = n–1 dan persamaan terakhir sistem (2.13). Mari kita tuliskan:

Oleh itu, tidak termasuk Xn-1, kami dapati

Seterusnya, menggunakan formula (2.14) dan pekali sapuan yang sebelum ini dikira menggunakan formula (2.15), (2.16), kami mengira secara berurutan semua yang tidak diketahui Xn- 1, xn-2 ,....,X 1. Algoritma untuk menyelesaikan sistem persamaan linear bentuk (2.13) dengan kaedah sapu ditunjukkan dalam Rajah. 2.4.

nasi. 2.4. Algoritma kaedah sapuan

Apabila menganalisis algoritma kaedah sapuan, seseorang mesti mengambil kira kemungkinan pembahagian dengan sifar dalam formula (2.15), (2.16). Ia boleh ditunjukkan bahawa jika keadaan penguasaan unsur pepenjuru dipenuhi, i.e. if , dan untuk sekurang-kurangnya satu nilai i ketidaksamaan yang ketat berlaku, pembahagian dengan sifar tidak berlaku, dan sistem (2.13) mempunyai penyelesaian yang unik.

Syarat yang diberikan untuk penguasaan unsur pepenjuru juga memastikan kestabilan kaedah sapuan berkenaan dengan ralat pembundaran. Keadaan terakhir membolehkan kita menggunakan kaedah sapuan untuk menyelesaikan sistem yang besar persamaan. Ambil perhatian bahawa syarat untuk kestabilan sapuan ini adalah mencukupi, tetapi tidak perlu. Dalam beberapa kes, untuk sistem berhawa dingin dalam bentuk (2.13), kaedah sapuan ternyata stabil walaupun keadaan dominasi unsur pepenjuru dilanggar.

Kaedah berangka algebra linear

3. Kaedah berjalan

Kaedah sapuan ialah algoritma yang mudah dan berkesan untuk menyelesaikan sistem linear persamaan algebra dengan matriks pekali tridiagon dalam bentuk berikut

Sistem jenis ini sering timbul apabila menyelesaikan pelbagai masalah kejuruteraan, contohnya, apabila menginterpolasi fungsi dengan spline.

Mari kita tukarkan persamaan pertama sistem (8) kepada bentuk x 1 = 1 x 2 + 1, di mana

1 = -c 1 / b 1 dan 1 = -d 1 / b 1 . Mari kita gantikan ungkapan yang diperoleh untuk x 1 ke dalam persamaan kedua sistem (8)

a 2 (1 x 2 + 1) + b 2 x 2 + c 2 x 3 = d 2 .

Mari kita kemukakan persamaan ini dalam bentuk x 2 = 2 x 3 + 2, di mana 2 = -c 2 / (b 2 + a 2 1) dan 2 = (d 2 - a 2 1) / (b 2 + a 2 1 ). Kami menggantikan ungkapan yang diperolehi untuk x 2 ke dalam persamaan ketiga sistem (8), dsb.

Pada langkah ke-i (1< i < n) процесса persamaan ke-i sistem mengambil bentuk

x i = i x i+1 + i , (9)

di mana i = -с i / (b i + a i i-1) dan i = (d i - a i i-1) / (b i + a i i-1).

Pada yang terakhir langkah ke- menggantikan ungkapan x n -1 = n -1 x n + n -1 ke dalam persamaan terakhir sistem (8) memberikan persamaan a n (n -1 x n + n -1) + b n x n = d n , daripada mana kita boleh menentukan nilai x n = n = (d n - a n n-1) / (b n + a n n-1).

Nilai baki x i yang tidak diketahui (i = n-1, n-2, ..., 1) mudah dikira menggunakan formula (9).

Oleh itu, algoritma sapuan, seperti kaedah Gaussian, merangkumi dua peringkat - langkah ke hadapan (sapu ke hadapan) dan gerakan terbalik (sapu terbalik).

Proses langsung kaedah sapuan terdiri daripada pengiraan pekali sapuan

i (i =) dan i (i =).

Untuk i = 1, pekali ini dikira menggunakan formula:

1 = -c 1 / 1 ; 1 = -d 1 / 1 ; 1 = b 1 .

Untuk i = formula pengulangan berikut digunakan:

i = -с i / i ; i = (d i - a i i-1) / i ; i = b i + a i i-1 .

Sapuan ke hadapan berakhir pada i = n:

n = (d n - a n n-1) / n ; n = b n + a n n-1 .

Pukulan songsang Kaedah sapuan membolehkan anda mengira nilai yang tidak diketahui. Mula-mula kita andaikan x n = n. Kemudian masuk susunan terbalik menggunakan formula (9), nilai yang tidak diketahui x n -1, x n -2, ..., x 1 ditentukan.

Sifat kaedah sapuan. Kerumitan kaedah sapuan dianggarkan lebih kurang 8n operasi aritmetik, yang penting kaedah kurang Gauss. Kewujudan penyelesaian kepada sistem (8) dan keunikannya terjamin apabila syarat yang mencukupi, diberikan oleh teorem berikut.

Teorem. Biarkan pekali sistem (8) memenuhi ketaksamaan berikut

b k a k +c k ; b k >a k ; k = , di mana a 1 = 0; b n = 0. Kemudian i 0 dan i

1 untuk semua i =

Ambil perhatian bahawa untuk semua i 0, pengiraan menggunakan formula sapuan terus boleh diselesaikan (tiada satu pun penyebut akan pergi ke sifar). Pada masa yang sama, semua pekali i supaya i 1 memastikan kestabilan mengikut data input peringkat sapuan ke belakang mengikut formula (9).

Matematik pengiraan

Kaedah membahagikan segmen kepada separuh adalah cara yang paling mudah dan boleh dipercayai untuk menyelesaikan persamaan tak linear. Biarkan diketahui daripada analisis awal bahawa punca persamaan (2.1) berada pada segmen , iaitu x*, supaya f(x*) = 0...

Matematik pengiraan

Kaedah Newton adalah yang paling banyak kaedah yang berkesan menyelesaikan persamaan tak linear. Biarkan x* menjadi punca supaya f(a)f(b)< 0. Предполагаем, что функция f(x) непрерывна на отрезке и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b...

Matematik pengiraan

Dalam ini dan bahagian seterusnya Mari kita pertimbangkan pengubahsuaian kaedah Newton. Seperti yang dapat dilihat daripada formula (2.13), kaedah Newton memerlukan pengiraan derivatif untuk pelaksanaannya, yang mengehadkan penggunaannya. Kaedah secant tidak mempunyai kelemahan ini...

Kaedah carian minimum global, dipanggil kaedah carian grid, boleh dipercayai, tetapi hanya boleh digunakan untuk masalah dimensi rendah (n<4). Неправильный выбор начального шага сетки может привести к тому...

Pengaturcaraan linear dan bukan linear

Lelaran 1. Bilangan lelaran k = 0 Lelaran 2. Bilangan lelaran k = 1 Carian selesai 3.3...

Permodelan matematik dan kaedah berangka dalam menyelesaikan masalah teknikal

Maklumat teori. Menyelesaikan persamaan pembezaan y/=f(x,y) dengan kaedah berangka bermakna, untuk jujukan argumen x0, x1..., xn dan nombor y0, tanpa mentakrifkan fungsi y=F(x), cari nilai berikut y1, y2,..., уn bahawa уi=F(xi)(i=1,2,…, n) dan F(x0)=y0...

Pemodelan matematik semasa eksperimen aktif

Simpleks sekata dalam ruang En ialah set n+1 titik (bucu simpleks) yang sama jarak antara satu sama lain. Segmen yang menghubungkan dua bucu dipanggil tepi simpleks...

Pengaturcaraan matematik

Kaedah Newton, algoritma Newton (juga dikenali sebagai kaedah tangen) ialah kaedah berangka berulang untuk mencari punca (sifar) bagi fungsi tertentu. Untuk menyelesaikan persamaan f(x)=0 secara berangka menggunakan lelaran mudah...

Kaedah putaran untuk menyelesaikan SLAE

Kaedah transformasi geometri untuk menyelesaikan masalah pembinaan geometri

Mari kita pertimbangkan satu lagi transformasi geometri - penyongsangan, yang memungkinkan untuk menyelesaikan beberapa masalah pembinaan yang agak kompleks yang sukar diselesaikan menggunakan teknik lain yang telah kami pertimbangkan...

Menyelesaikan Persamaan Parabola

Mari kita pertimbangkan satu kes khas masalah yang dikemukakan dalam bahagian sebelumnya. Di rantau ini, cari penyelesaian kepada persamaan dengan syarat sempadan dan keadaan awal. Mari kita pertimbangkan skim pengkomputeran yang stabil...

Sistem persamaan pembezaan dengan pekali malar

Setakat ini kita telah menyelesaikan satu persamaan linear dengan pekali malar. Ternyata, bagaimanapun, sistem persamaan linear yang sangat umum dengan pekali malar boleh dikurangkan kepada satu persamaan...

Analisis sistem kumpulan transformasi keadaan Rubik's Cube

CFOP ialah nama empat peringkat pemasangan (Rajah 3.2): Palang, F2L, OLL, PLL: 1) Palang - pemasangan salib...

Kaedah berangka algebra linear

Kaedah sapuan ialah algoritma yang mudah dan berkesan untuk menyelesaikan sistem persamaan algebra linear dengan matriks tridiagonal pekali dalam bentuk berikut (8) Sistem jenis ini sering timbul apabila menyelesaikan pelbagai...

Kaedah berangka untuk menyelesaikan persamaan transendental

Biarkan persamaan (1) mempunyai punca pada selang, dan f (x) dan f "(x) adalah selanjar dan mengekalkan tanda malar sepanjang keseluruhan selang. Maksud geometri kaedah Newton ialah lengkok lengkok y = f (x) digantikan dengan tangen.

Kaedah ini juga merupakan pengubahsuaian kaedah Gauss untuk kes khas jarang sistem - sistem dengan matriks jenis tridiagonal (masalah nilai sempadan DE).

Bentuk kanonik rakaman mereka

(1.6)

atau dalam bentuk yang diperluaskan:

(1.7)

Dalam kes ini, sebagai peraturan, semua pekali b i  0.

Kaedah ini dilaksanakan dalam dua peringkat - pukulan hadapan dan belakang.

Pukulan lurus . Setiap tidak diketahui x i dinyatakan melalui x i +1

(x i = A i x i +1 + B i Untuk i = 1,2, ..., n– 1) (1.8)

melalui pekali larian A i Dan B i. Mari kita tentukan algoritma untuk pengiraan mereka.

Daripada persamaan pertama sistem (1.7) kita dapati x 1:

.

Daripada persamaan (1.8) di i = 1 x 1 = A 1  x 2 + B 1. Oleh itu,

dan mengikut persamaan (1.8) dengan i = 2 x 2 = A 2 x 3 + B 2, oleh itu:

,

di mana e 2 = A 2 A 1 + b 2 .

Memfokuskan pada nisbah indeks untuk pekali persamaan (1.9) dan (1.9*), kita boleh mendapatkan hubungan ini untuk kes umum:

,

di mana e i = A i  A i –1 + b i (i= 2,3, ..., n– 1) . (1.10)

Pergerakan terbalik. Daripada persamaan terakhir sistem (1.7) menggunakan data ungkapan (1.8) dengan i = n – 1

.

Apabila melaksanakan kaedah sapuan, ia mesti diambil kira, dengan syarat

(1.12)

atau sekurang-kurangnya untuk satu b i ketidaksamaan ketat (1.12) berlaku, pembahagian dengan "0" dihapuskan, dan sistem mempunyai penyelesaian yang unik.

Ambil perhatian bahawa syarat (1.12) adalah mencukupi, tetapi tidak perlu. Dalam beberapa kes, untuk sistem berhawa dingin (1.7), kaedah sapuan boleh stabil walaupun syarat (1.12) tidak dipenuhi.

Gambar rajah algoritma kaedah sapuan mungkin kelihatan seperti yang ditunjukkan dalam Rajah 1.2.

Rajah 1.2 - Gambar rajah blok kaedah sapuan

Kaedah berulang untuk menyelesaikan slough

Kelebihan kaedah lelaran ialah kebolehgunaannya pada sistem yang tidak bersyarat dan sistem tertib tinggi, pembetulan sendiri dan kemudahan pelaksanaan pada komputer. Untuk memulakan pengiraan, kaedah berulang memerlukan penentuan beberapa anggaran awal kepada penyelesaian yang dikehendaki.

Perlu diingatkan bahawa keadaan dan kadar penumpuan proses lelaran amat bergantung pada sifat matriks. A sistem dan pada pilihan anggaran awal.

Untuk menggunakan kaedah lelaran, sistem asal mesti dibawa ke bentuk lelaran

(1.13)

dan kemudian lakukan proses berulang menggunakan formula berulang:

, k = 0, 1, 2, ... . (1.13*)

Matriks G dan vektor diperoleh hasil daripada transformasi sistem asal.

Untuk penumpuan kaedah (1.13*) adalah perlu dan memadai bahawa | i (G)| < 1, где  i (G) - semua nilai eigen matriks G. Penumpuan juga akan berlaku jika || G|| < 1, ибо | i (G)| <  ||G||

( - mana-mana).

||G|| =
Simbol ||...|| bermaksud norma matriks. Apabila menentukan nilainya, mereka selalunya berhenti pada memeriksa dua syarat: G|| =
, (1.14)

di mana
atau || A. Konvergensi juga dijamin jika matriks asal

. (1.15)

mempunyai penguasaan pepenjuru, i.e.
Apabila keadaan (1.14) atau (1.15) dipenuhi, kaedah lelaran menumpu untuk sebarang anggaran awal
. Selalunya vektor ambil sama ada sifar atau unit, atau vektor itu sendiri

daripada sistem (1.13). i Jika keadaan (1.15) dipenuhi, maka transformasi kepada bentuk lelaran (1.13) boleh dilakukan hanya dengan menyelesaikan setiap x i persamaan sistem (1) berkenaan dengan

mengikut formula berulang berikut: g = − ij g / ij a ; mengikut formula berulang berikut: a = 0; ii i = b i / ij a , (1.15*)

f
.

i.e. A Jika dalam matriks

tiada penguasaan pepenjuru; ia mesti dicapai melalui beberapa transformasi linearnya yang tidak melanggar kesetaraan mereka.

Tujuan. Perkhidmatan ini bertujuan untuk menyelesaikan masalah pengaturcaraan dinamik menggunakan kaedah ke hadapan dan ke belakang dalam mod dalam talian (lihat contoh penyelesaian masalah pengagihan pelaburan yang optimum). Arahan. Pilih bilangan objek dan bilangan kumpulan pilihan yang mungkin, klik Seterusnya. Dalam tetingkap baharu pilih.

kaedah sapuan 2 3 4 5 6 7 8 9 10 Bilangan objek 2 3 4 5 6 7 8 9 10

Seterusnya
F(x 1 ,x 2 ,x 3) = f 1 (x 1) + f 2 (x 2) + f 3 (x 3) → maks
x 1 + 2x 2 + 2x 3 ≤ 5

X	0	1	2	3	4	5
f 1 (x 1)	6	7	11	12	15	16
f 2 (x 2)	9	11	13	15
f 3 (x 3)	8	12	14	16

Penyelesaian.
Peringkat I. Pengoptimuman bersyarat. f 1 (L) = maks(f 1); 0 ≤ x 1 ≤ 5; x 1 = 0,1,2,3,4,5.
f 1 (0) = maks = 6
f 1 (1) = maks = 7
f 1 (2) = maks = 11
f 1 (3) = maks = 12
f 1 (4) = maks = 15
f 1 (5) = maks = 16
Jadual 1 – Pengiraan nilai fungsi f 1 (L)

L	0	1	2	3	4	5
f 1 (L)	6	7	11	12	15	16
x 1	0	1	2	3	4	5

f 2 (L) = maks; 0 ≤ x 2 ≤ 5; x 2 = 0,1,2,3,4,5.
f 2 (0) = maks = 15
f 2 (1) = maks = 16
f 2 (2) = maks = 20
f 2 (3) = maks = 21
f 2 (4) = maks = 24
f 2 (5) = maks = 25
Jadual 2 - Pengiraan nilai fungsi f 2 (L)

L	0	1	2	3	4	5
f2(L)	15	16	20	21	24	25
x 2	0	0	0	0	0	0

f 3 (L) = maks; 0 ≤ x 3 ≤ 5; x 3 = 0,1,2,3,4,5.
f 3 (0) = maks = 23
f 3 (1) = maks = 24
f 3 (2) = maks = 28
f 3 (3) = maks = 29
f 3 (4) = maks = 32
f 3 (5) = maks = 33
Jadual 3 - Pengiraan nilai fungsi f 3 (L)

L	0	1	2	3	4	5
f 3 (L)	23	24	28	29	32	33
x 3	0	0	0	0	0	0

Peringkat II. Pengoptimuman tanpa syarat.
Oleh itu, maksimum ialah f 3 (5) = 33
Dalam kes ini, x 3 = 0, kerana f 3 (5) = 33 dicapai pada x 3 = 0 (lihat Jadual 3).
Baki x diedarkan seperti berikut:
L = 5 - 2 * 0 = 5
f 2 (5) = 25 dicapai pada x 2 = 0 (lihat jadual 2).
L = 5 - 2 * 0 = 5
f 1 (5) = 16 dicapai pada x 1 = 5 (lihat jadual 1).
L = 5 - 1 * 5 = 0
Hasilnya, pilihan terbaik dicapai dengan nilai: x 1 = 5, x 2 = 0, x 3 = 0

Contoh No. 2. Mari kita pertimbangkan masalah peruntukan optimum modal K = nh dalam m dana bebas yang berbeza (bank, organisasi, firma, dll.), yang mana jangkaan keuntungan f i diketahui untuk pelaburan modal x i = ih, i = 1.. n. Di sini n ialah bilangan kenaikan diskret h (diskrit) di mana modal K dibahagikan.
Biarkan data sedemikian tersedia untuk empat (m=4) dana untuk h = 1 juta rubel, n = 6

Penyelesaian.
Peringkat I. Pengoptimuman bersyarat.
Langkah pertama: k = 4.
Mari kita anggap bahawa semua dana dalam jumlah x 4 = 6 diberikan kepada perusahaan ke-4. Dalam kes ini, pendapatan maksimum, seperti yang boleh dilihat dari Jadual 1*, ialah 0.56, oleh itu:
F 4 (c 4) = g 4 (x 4)
Jadual 1.

0	x 1	0	1	2	3	4	5	6
x 4	f 0 (x 0) / F 4 (x 4)	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
1	0.2	0	0	0	0	0	0.2	0
2	0.33	0	0	0	0	0.33	0	0
3	0.42	0	0	0	0.42	0	0	0
4	0.48	0	0	0.48	0	0	0	0
5	0.53	0	0.53	0	0	0	0	0
6	0.56	0.56*	0	0	0	0	0	0

Jadual 1*.

c 1	0	1	2	3	4	5	6
F 0 (c 1)	0	0.2	0.33	0.42	0.48	0.53	0.56
x 1	0	1	2	3	4	5	6

Langkah ke-2: k = 3.

F 3 (c 3) = maks [ g 3 (x 3) + F 4 (c 3 - x 3)]
Jadual 2.

0	x 2	0	1	2	3	4	5	6
x 3	f 3 (x 3) / F 3 (x 3)	0	0.2	0.33	0.42	0.48	0.53	0.56
0	0	0	0.2*	0.33	0.42	0.48	0.53	0.56
1	0.15	0.15	0.35*	0.48*	0.57	0.63	0.68	0
2	0.25	0.25	0.45	0.58	0.67	0.73	0	0
3	0.4	0.4	0.6*	0.73*	0.82	0	0	0
4	0.5	0.5	0.7	0.83*	0	0	0	0
5	0.62	0.62	0.82	0	0	0	0	0
6	0.73	0.73	0	0	0	0	0	0

Isikan jadual 2*. Untuk melakukan ini, pada setiap pepenjuru timur laut kita dapati nombor terbesar, yang kita tandakan dengan asterisk dan menunjukkan nilai yang sepadan x 2.
Jadual 2*.

c 2	0	1	2	3	4	5	6
F 3 (c 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
x 2	0	0	1	1	3	3	4

Langkah ke-3: k = 2.
Kami menentukan strategi optimum untuk mengagihkan dana antara perusahaan lain. Dalam kes ini, hubungan berulang Bellman mempunyai bentuk:
F 2 (c 2) = maks [ g 2 (x 2) + F 3 (c 2 - x 2)]
Jadual 3.

0	x 3	0	1	2	3	4	5	6
x 2	f 4 (x 4) / F 2 (x 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
0	0	0	0.2	0.35	0.48	0.6	0.73	0.83
1	0.25	0.25*	0.45*	0.6	0.73	0.85	0.98	0
2	0.41	0.41	0.61*	0.76*	0.89	1.01	0	0
3	0.55	0.55	0.75	0.9*	1.03*	0	0	0
4	0.65	0.65	0.85	1	0	0	0	0
5	0.75	0.75	0.95	0	0	0	0	0
6	0.8	0.8	0	0	0	0	0	0

Isikan jadual 3*. Untuk melakukan ini, pada setiap pepenjuru timur laut kita dapati nombor terbesar, yang kita tandakan dengan asterisk dan menunjukkan nilai yang sepadan x 3.
Jadual 3*.

c 3	0	1	2	3	4	5	6
F 4 (c 3)	0	0.25	0.45	0.61	0.76	0.9	1.03
x 3	0	1	1	2	2	3	3

Langkah ke-4: k = 1.
Kami menentukan strategi optimum untuk mengagihkan dana antara perusahaan lain. Dalam kes ini, hubungan berulang Bellman mempunyai bentuk:
F 1 (c 1) = maks [ g 1 (x 1) + F 2 (c 1 - x 1)]
Jadual 4.

0	x 4	0	1	2	3	4	5	6
x 1	f 5 (x 5) / F 1 (x 1)	0	0.25	0.45	0.61	0.76	0.9	1.03
0	0	0	0.25	0.45	0.61	0.76	0.9	1.03
1	0.28	0.28*	0.53*	0.73*	0.89	1.04	1.18	0
2	0.45	0.45	0.7	0.9	1.06	1.21	0	0
3	0.65	0.65	0.9*	1.1*	1.26*	0	0	0
4	0.78	0.78	1.03	1.23	0	0	0	0
5	0.9	0.9	1.15	0	0	0	0	0
6	1.02	1.02	0	0	0	0	0	0

Isikan jadual 4*. Untuk melakukan ini, pada setiap pepenjuru timur laut kita dapati nombor terbesar, yang kita tandakan dengan asterisk dan menunjukkan nilai yang sepadan x 4.
Jadual 4*.

c 4	0	1	2	3	4	5	6
F 5 (c 4)	0	0.28	0.53	0.73	0.9	1.1	1.26
x 4	0	1	1	1	3	3	3

Peringkat II. Pengoptimuman tanpa syarat.
Langkah pertama: k = 1.
Menurut Jadual 4*, pendapatan maksimum apabila mengagihkan 6 antara perusahaan ialah c 1 = 6, F 1 (6) = 1.26. Dalam kes ini, perusahaan pertama perlu diperuntukkan x 1 = 3.
Langkah ke-2: k = 2.

c 2 = c 1 - x 1 = 6 - 3 = 3.
Menurut Jadual 3*, pendapatan maksimum apabila mengagihkan 3 antara perusahaan ialah c 2 = 3, F 2 (3) = 0.61. Dalam kes ini, perusahaan ke-2 perlu memperuntukkan x 2 = 2.
Langkah ke-3: k = 3.
Mari kita tentukan jumlah baki dana yang boleh diagihkan kepada baki perusahaan.
c 3 = c 2 - x 2 = 3 - 2 = 1.
Menurut Jadual 2*, pendapatan maksimum apabila mengagihkan 1 antara perusahaan ialah c 3 = 1, F 3 (1) = 0.2. Dalam kes ini, perusahaan ke-3 perlu diperuntukkan x 3 = 0.
Langkah ke-4: k = 4.
Mari kita tentukan jumlah baki dana yang boleh diagihkan kepada baki perusahaan.
c 4 = c 3 - x 3 = 1 - 0 = 1.
Menurut Jadual 1*, pendapatan maksimum apabila mengagihkan 1 antara perusahaan ialah c 4 = 1, F 4 (1) = 0.20. Dalam kes ini, perusahaan ke-4 perlu diperuntukkan x 4 = 1.
Oleh itu, pelan pelaburan optimum untuk perusahaan ialah:
x 1 = 3
x 2 = 2
x 3 = 0
x 4 = 1
yang akan memberikan pendapatan maksimum bersamaan dengan: F(6) = g 1 (3) + g 2 (2) + g 3 (0) + g 4 (1) = 0.65 + 0.41 + 0 + 0.20 = 1.26.

Algoritma paling mudah untuk mengira penyelesaian perbezaan adalah untuk skema eksplisit. Walau bagaimanapun, kaedah eksplisit adalah stabil hanya untuk perhubungan tertentu antara langkah grid. Memenuhi keperluan kestabilan membawa kepada keperluan untuk pendiskretan yang sangat halus bagi pembolehubah masa, yang meningkatkan masa pengiraan.

Skim tersirat, sebagai peraturan, bebas daripada kelemahan ini dan membenarkan pemilihan langkah grid bebas dalam masa dan ruang. Walau bagaimanapun, pada setiap lapisan (lelaran) adalah perlu untuk menyelesaikan sistem persamaan algebra dengan bilangan yang tidak diketahui sama dengan bilangan nod pada lapisan yang sedang dipertimbangkan. Jika anda tidak mengambil kira keistimewaan sistem ini (matriks sparsity) dan menyelesaikannya sebagai sistem umum, maka sejumlah besar operasi aritmetik akan diperlukan.

Kaedah yang berkesan untuk menyelesaikan sistem persamaan yang dijana oleh skema perbezaan ialah kaedah sapuan. Mari kita pertimbangkan algoritmanya menggunakan contoh penyelesaian perbezaan kepada masalah nilai sempadan pertama untuk persamaan haba. Untuk masalah nilai sempadan dalam kawasan segi empat tepat

pertimbangkan skema perbezaan tersirat

Di sini Ai = Ci = 1, Bi = 1 + /?. 2 /(2at), D = li 2 (-u"- g/")/(2at). Dalam kes kami A j, D dan C* tidak bergantung pada indeks i, walau bagaimanapun, jika langkah grid berubah, maka semua pekali akan bergantung pada nombor nod. Adalah penting untuk ambil perhatian bahawa A(, Bj, Ci, g n+l, / n+1 ialah kuantiti yang diketahui. Hubungan (7.2) ialah sistem persamaan linear untuk Uq + , Mdg + yang tidak diketahui.

Matriks yang diperluaskan sistem ini mempunyai bentuk

Dalam matriks ini, unsur bukan sifar terletak di sepanjang pepenjuru utama dan dua yang bersebelahan. Matriks jenis ini dipanggil segi tiga.

Kehadiran keadaan sempadan kiri (mq +1 = n+1) membolehkan kita mencari penyelesaian dalam bentuk (untuk kesederhanaan tatatanda, superskrip yang tidak diketahui ditinggalkan) hubungan

Ia dipanggil nisbah berjalan, dan pekali yang termasuk di dalamnya ialah A"*_i dan Li- - pekali pemanduan. Untuk i = 1 (7.1) berpuas hati jika kami menerima

Dengan cara ini nilai awal kemungkinan perlumbaan ditetapkan.

Mari kita hapuskan yang tidak diketahui dengan bantuan hubungan (7.3) sch-1 daripada (7.2):

Menjalankan penjelmaan algebra yang paling mudah, kami memperoleh

dalam bentuk yang bertepatan dengan nisbah pemanduan. Perbandingan (7.5) dan (7.3) memberikan hubungan berulang untuk pekali sapuan:

Menggunakan nilai awal Co. = 0, Lq = , boleh dikira secara berurutan K, L], KEPADA2 , ^2, ..., Ln- - komponen vektor pekali larian. Proses pengiraan ini dipanggil lari langsung. Adalah mudah untuk melihat bahawa sapuan terus dengan bantuan transformasi asas mengubah matriks tridiagonal sistem linear asal kepada satu dwidiagon atas, dan bilangan operasi aritmetik (disebabkan oleh bentuk khas matriks asal) adalah berkadar dengan bilangan yang tidak diketahui 1 .

Bentuk bidiagon bagi matriks yang terhasil memudahkan untuk membina proses pengiraan yang tidak diketahui. Menjalankan hubungan untuk nod terakhir wjv-i = Kn-Un + L^~ 1, bersama-sama dengan keadaan sempadan yang betul = saya, membolehkan anda mengira idg_ 1, dan kemudian, menggunakan formula berulang (7.3), tentukan semua yang tidak diketahui secara berurutan un-2, un-3, ..., sch masalah perbezaan. Pengiraan berurutan bagi yang tidak diketahui menggunakan hubungan sapuan (7.3) dipanggil larian terbalik. Pada terasnya, kaedah sapuan ialah varian penyingkiran Gaussian, yang mengambil kira ciri-ciri struktur matriks tridiagonal dan menghapuskan operasi pada unsur sifarnya.

Adalah mudah untuk melihat bahawa apabila menyelesaikan sistem linear dengan matriks tridiagonal dengan kaedah sapuan, bilangan operasi aritmetik adalah berkadar dengan bilangan nod grid perbezaan oleh itu, penggunaan kaedah sapuan memungkinkan untuk membina skim perbezaan ekonomi.

Satu lagi keadaan penting, buktinya boleh didapati dalam literatur khusus, ialah kestabilan pengiraan kaedah sapuan. Ini bermakna bahawa ketepatan penyelesaian yang terhasil akan sama dengan ketepatan pengiraan pertengahan yang dilakukan.

Kaedah sapuan pertama kali dicadangkan oleh ahli matematik Soviet Gelfond dan Lokutsievsky pada tahun 1950-an untuk penyelesaian berangka masalah nilai sempadan. Keberkesanan kos dan kestabilan kaedah menjadikannya pada satu masa elemen utama untuk menyelesaikan skema perbezaan tersirat. Aplikasi idea pembahagian kepada pembolehubah spatial memungkinkan untuk melanjutkan algoritma prognostik ke kelas masalah multidimensi. Dalam beberapa tahun kebelakangan ini, terima kasih kepada pertumbuhan pesat sumber pengkomputeran (terutamanya dalam RAM), algoritma lain untuk menyelesaikan sistem algebra berdimensi tinggi dengan matriks jarang telah digunakan secara meluas, yang, tidak seperti kaedah sapuan, tidak terikat dengan ketat seperti itu. keperluan sebagai tridiagonal.

• Penyimpangan daripada bidiagonal untuk pembolehubah terakhir dalam kes keadaan sempadan jenis kedua atau ketiga mudah diatasi.
• Keadaan kestabilan dipenuhi jika matriks mempunyai sifat penguasaan pepenjuru. Sifat ini dipegang untuk matriks yang dijana oleh skema perbezaan kelas yang sedang dipertimbangkan.