phương pháp quét là một sửa đổi của phương pháp Gauss cho một trường hợp cụ thể của các hệ thống thưa thớt - một hệ phương trình với ma trận tam giác. Những hệ thống như vậy có được bằng cách mô hình hóa một số nhiệm vụ kỹ thuật, cũng như tại giải pháp số bài toán giá trị biên cho phương trình vi phân.

Ta viết hệ phương trình dưới dạng

Trên đường chéo chính của ma trận của hệ thống này là các phần tử b 1, b 2, …, tỷ, phía trên nó là các phần tử Với1, s2,... , sN-1 bên dưới nó là các yếu tố MỘT 2, MỘT 3,... , hướng lên(trong trường hợp này, thông thường tất cả các hệ số bi không bằng 0). Các phần tử còn lại của ma trận bằng không.

phương pháp quét bao gồm hai giai đoạn - chạy thẳng(tương tự như di chuyển trực tiếp của phương pháp Gauss) và quét ngược(tương tự như chuyển động ngược của phương pháp Gauss). Chuyển tiếp quét bao gồm việc tính toán các hệ số quét trí tuệ nhân tạo,bí, với sự trợ giúp của mỗi x chưa biết Tôi thể hiện qua tử+1 :

Từ phương trình thứ nhất của hệ (2.13) ta tìm được

Mặt khác, theo công thức (2.14) Đánh đồng các hệ số trong cả hai biểu thức cho X 1, chúng tôi nhận được

(2.15)

Hãy để chúng tôi thay thế vào phương trình thứ hai của hệ thống (2.13) thay vì X 1 biểu hiện của mình thông qua X 2 theo công thức (2.14):

Thể hiện từ đây X 2 qua X 3:

Hệ số quét được tính tương tự cho bất kỳ số nào Tôi:

(2.16)

Quét ngược bao gồm tính toán tuần tự các ẩn số xi. Đầu tiên bạn cần tìm xp.Để làm điều này, chúng tôi sử dụng biểu thức (2.14) cho Tôi = P–1 và phương trình cuối của hệ (2.13). Hãy viết chúng ra:

Do đó, loại trừ Xn-1, chúng ta tìm thấy

Tiếp theo, sử dụng các công thức (2.14) và các hệ số quét đã tính trước đó theo các công thức (2.15), (2.16), ta tính tuần tự tất cả các ẩn số XN- 1, xn-2 ,....,X 1. Thuật toán giải hệ thống Các phương trình tuyến tính của dạng (2.13) bằng phương pháp quét được thể hiện trong hình. 2.4.

Cơm. 2.4. Thuật toán phương pháp quét

Khi phân tích thuật toán của phương pháp quét, cần tính đến khả năng chia hết cho 0 trong các công thức (2.15), (2.16). Có thể chỉ ra rằng với điều kiện phổ biến của các phần tử đường chéo, tức là if và cho ít nhất một giá trị Tôi bất đẳng thức nghiêm ngặt xảy ra, phép chia cho 0 không xảy ra và hệ (2.13) có nghiệm duy nhất.

Điều kiện trên đối với ưu thế của các phần tử đường chéo cũng đảm bảo tính ổn định của phương pháp quét đối với các lỗi làm tròn. Trường hợp thứ hai cho phép chúng ta sử dụng phương pháp quét để giải quyết hệ thống lớn phương trình. Lưu ý rằng điều kiện này cho sự ổn định của quá trình quét là đủ, nhưng không cần thiết. Trong một số trường hợp, đối với các hệ điều kiện tốt có dạng (2.13), phương pháp quét hóa ra là ổn định ngay cả khi điều kiện về sự phổ biến của các phần tử đường chéo bị vi phạm.

Phương pháp số của đại số tuyến tính

3. Phương pháp quét

Phương pháp quét là một thuật toán đơn giản và hiệu quả để giải các hệ phương trình tuyến tính phương trình đại số với các ma trận hệ số tam giác có dạng sau

Các hệ thống thuộc loại này thường phát sinh khi giải quyết các vấn đề kỹ thuật khác nhau, chẳng hạn như khi nội suy các hàm bằng splines.

Hãy biến đổi phương trình đầu tiên của hệ (8) thành dạng x 1 = 1 x 2 + 1, trong đó

1 = -c 1 / b 1 và 1 = -d 1 / b 1 . Ta thế biểu thức thu được của x 1 vào phương trình thứ hai của hệ (8)

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

Hãy biểu diễn phương trình này dưới dạng x 2 \u003d 2 x 3 + 2, trong đó 2 \u003d -c 2 / (b 2 + a 2 1) và 2 \u003d (d 2 - a 2 1) / (b 2 + một 2 1). Chúng ta thay biểu thức thu được cho x 2 vào phương trình thứ ba của hệ (8), v.v.

Tại bước thứ i (1< i < n) процесса phương trình thứ i hệ thống có dạng

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

trong đó i = -с i / (b i + a i i-1) và i = (d i - a i i-1) / (b i + a i i-1).

Vào cuối bước thứ n thế vào phương trình cuối cùng của hệ (8) của biểu thức x n -1 = n -1 x n + n -1 ta được phương trình a n (n -1 x n + n -1) + b n x n = d n, từ đó xác định được giá trị x n = n = (d n - a n n-1)/(b n + a n n-1).

Giá trị của các ẩn số còn lại x i (i=n-1, n-2, ..., 1) được tính dễ dàng bằng công thức (9).

Do đó, thuật toán quét, giống như phương pháp Gauss, bao gồm hai giai đoạn - di chuyển về phía trước (quét về phía trước) và di chuyển ngược lại (quét ngược).

Bước trực tiếp của phương pháp quét là tính các hệ số quét

tôi (i =) và tôi (i =).

Với i = 1, các hệ số này được tính theo công thức:

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

Đối với i = các công thức đệ quy sau đây được sử dụng:

tôi \u003d -c tôi / tôi; i = (d i - a i i-1) / i ; i = b i + a i i -1 .

Chuyển tiếp quét kết thúc khi i = n:

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

Đảo ngược phương pháp quét cho phép bạn tính toán các giá trị của ẩn số. Đầu tiên, x n = n được giả định. Sau đó trong thứ tự đảo ngược theo công thức (9) xác định giá trị của các ẩn số x n -1 , x n -2 , ..., x 1 .

Thuộc tính phương pháp quét. Độ phức tạp của phương pháp quét được ước tính vào khoảng 8n phép tính số học, điều này có ý nghĩa ít phương pháp Gauss. Sự tồn tại nghiệm của hệ (8) và tính duy nhất của nó được đảm bảo nếu đủ điều kiệnđược cho bởi định lý sau.

định lý. Để các hệ số của hệ (8) thỏa mãn các bất phương trình sau

bk a k + c k ; b k > a k ; k = , với 1 = 0; b n = 0. Khi đó i 0 và i

1 cho tất cả tôi =

Lưu ý rằng với tất cả i 0, các phép tính bằng các công thức quét về phía trước có thể được hoàn thành (không có mẫu số nào biến mất). Đồng thời, tất cả các hệ số i sao cho i 1 mang lại sự ổn định đối với dữ liệu đầu vào của giai đoạn quét ngược theo công thức (9).

Toán học tính toán

Phương pháp chia đôi một đoạn là cách đơn giản nhất và đáng tin cậy nhất để giải phương trình phi tuyến tính. Hãy biết từ một phân tích sơ bộ rằng nghiệm của phương trình (2.1) nằm trên khoảng , tức là, x*, sao cho f(x*) = 0...

Toán học tính toán

Phương pháp của Newton là tốt nhất phương pháp hiệu quả nghiệm của phương trình phi tuyến. Đặt gốc là x* , sao cho f(a)f(b)< 0. Предполагаем, что функция f(x) непрерывна на отрезке и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b...

Toán học tính toán

Trong này và phần tiếp theo xem xét các sửa đổi của phương pháp Newton. Như có thể thấy từ công thức (2.13), phương pháp Newton yêu cầu tính đạo hàm để thực hiện, điều này hạn chế ứng dụng của nó. Phương pháp secant không có thiếu sót này ...

Phương pháp tìm kiếm tối thiểu toàn cầu, được gọi là phương pháp tìm kiếm lưới, là đáng tin cậy, nhưng chỉ áp dụng cho các vấn đề thấp chiều (n<4). Неправильный выбор начального шага сетки может привести к тому...

Lập trình tuyến tính và phi tuyến tính

Lần lặp 1. Số lần lặp k = 0 Lần lặp 2. Số lần lặp k = 1 Đã hoàn thành tìm kiếm 3.3...

Mô hình hóa toán học và phương pháp số trong việc giải quyết các vấn đề kỹ thuật

Thông tin lý thuyết. Để giải phương trình vi phân y/=f(x,y) có nghĩa là số cho một dãy các đối số x0, x1…, xn và số y0, mà không cần xác định hàm y=F(x), để tìm các giá trị như vậy y1, y2,…, уn, mà уi=F(xi)(i=1,2,…, n) và F(x0)=y0...

Mô hình toán học với thử nghiệm hoạt động

Một đơn hình thông thường trong không gian En là tập hợp gồm n + 1 điểm cách đều nhau (các đỉnh của đơn hình). Đoạn nối hai đỉnh được gọi là cạnh của một hình...

lập trình toán học

Phương pháp Newton, thuật toán Newton (còn gọi là phương pháp tiếp tuyến) là một phương pháp số lặp để tìm nghiệm nguyên (không) của một hàm số đã cho. Để giải phương trình f(x)=0 bằng phép lặp đơn giản...

Phương pháp xoay để giải SLAE

Phương pháp biến hình trong giải toán hình học xây dựng

Hãy xem xét một phép biến đổi hình học khác - phép nghịch đảo, giúp giải một số bài toán xây dựng tương đối phức tạp khó giải bằng các phương pháp khác mà chúng tôi đã xem xét ...

Giải phương trình parabol

Hãy xem xét một trường hợp cụ thể của vấn đề đặt ra trong phần trước. Tìm nghiệm của phương trình với điều kiện biên và điều kiện đầu trong miền. Hãy xem xét một sơ đồ tính toán ổn định ...

Hệ phương trình vi phân với hệ số hằng

Cho đến nay, chúng ta đã giải một phương trình tuyến tính với các hệ số không đổi. Tuy nhiên, hóa ra là một hệ phương trình tuyến tính rất tổng quát với các hệ số không đổi theo một nghĩa nào đó có thể được rút gọn thành một phương trình duy nhất...

Phân tích hệ thống các nhóm biến đổi trạng thái của khối Rubik

CFOP là tên gọi của 4 công đoạn lắp ráp (hình 3.2): Cross, F2L, OLL, PLL: 1) Cross - lắp ráp chéo...

Phương pháp sốđại số tuyến tính

Phương pháp quét là một thuật toán đơn giản và hiệu quả để giải các hệ phương trình đại số tuyến tính với ma trận hệ số tam giác có dạng sau (8) Các hệ kiểu này thường phát sinh khi giải các ...

Các phương pháp số để giải phương trình siêu việt

Để phương trình (1) có nghiệm trên đoạn thẳng và f (x) và f "(x) liên tục và giữ nguyên dấu không đổi trên toàn bộ khoảng. Ý nghĩa hình học của phương pháp Newton là cung của đường cong y \u003d f(x) được thay bằng một tiếp tuyến. ..

Phương pháp này cũng là một sửa đổi của phương pháp Gauss cho trường hợp cụ thể thưa thớt hệ thống - hệ thống có ma trận thuộc loại tam giác (vấn đề biên của DE).

Hình thức kinh điển của ký hiệu của họ

(1.6)

hoặc ở dạng mở rộng:

(1.7)

Trong trường hợp này, như một quy luật, tất cả các hệ số b Tôi  0.

Phương pháp này được thực hiện theo hai giai đoạn - tiến và lùi.

đột quỵ về phía trước . mọi điều chưa biết x Tôi thể hiện qua x Tôi +1

(x Tôi = MỘT Tôi x Tôi +1 + b Tôi Vì Tôi = 1,2, ..., N– 1) (1.8)

bằng hệ số quét MỘT Tôi Và b Tôi. Hãy để chúng tôi xác định một thuật toán để tính toán của họ.

Từ phương trình thứ nhất của hệ (1.7) ta tìm được x 1:

.

Từ phương trình (1.8) với Tôi = 1 x 1 = MỘT 1  x 2 + b 1 . Kể từ đây,

và theo phương trình (1.8) tại Tôi = 2 x 2 = MỘT 2 x 3 + b 2 , do đó:

,

Ở đâu e 2 = MỘT 2 MỘT 1 + b 2 .

Tập trung vào các tỷ lệ của các chỉ số tại các hệ số của phương trình (1.9) và (1.9*), chúng ta có thể thu được các tỷ lệ này cho trường hợp tổng quát:

,

Ở đâu e Tôi = MỘT Tôi  MỘT Tôi –1 + b Tôi (Tôi= 2,3, ..., N– 1) . (1.10)

Di chuyển ngược lại. Từ phương trình cuối của hệ (1.7) sử dụng dữ kiện của biểu thức (1.8) với Tôi = N – 1

.

Khi thực hiện phương pháp quét, cần tính đến điều kiện

(1.12)

hoặc ít nhất là cho một b Tôi bất đẳng thức nghiêm ngặt (1.12), phép chia cho "0" bị loại trừ và hệ có nghiệm duy nhất.

Lưu ý rằng điều kiện (1.12) là đủ nhưng không cần thiết. Trong một số trường hợp, đối với các hệ thống có điều kiện tốt (1.7), phương pháp quét có thể ổn định ngay cả khi điều kiện (1.12) không được thỏa mãn.

Sơ đồ thuật toán của phương pháp quét có thể trông giống sơ đồ trong Hình 1.2.

Hình 1.2 - Sơ đồ khối của phương pháp quét

Phương pháp lặp đi lặp lại để giải quyết slough

Ưu điểm của các phương pháp lặp là khả năng ứng dụng của chúng đối với các hệ thống kém điều kiện và hệ thống có trật tự cao, tự sửa lỗi và dễ thực hiện trên máy tính. Các phương pháp lặp lại để bắt đầu tính toán yêu cầu một số xấp xỉ ban đầu cho giải pháp mong muốn.

Cần lưu ý rằng các điều kiện và tốc độ hội tụ của quá trình lặp về cơ bản phụ thuộc vào các tính chất của ma trận MỘT hệ thống và về việc lựa chọn các xấp xỉ ban đầu.

Để áp dụng phương pháp lặp, hệ thống ban đầu phải được giảm xuống dạng lặp

(1.13)

và sau đó thực hiện quá trình lặp theo các công thức đệ quy:

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

ma trận g và véc tơ thu được do sự biến đổi của hệ thống ban đầu.

Để phương trình (1.13*) hội tụ cần và đủ sao cho | Tôi (g)| < 1, где  Tôi (g) - tất cả các giá trị riêng của ma trận g. Sự hội tụ cũng sẽ xảy ra nếu || g|| < 1, ибо | Tôi (g)| <  ||g|| ( - bất kỳ).

Ký hiệu ||...|| nghĩa là chuẩn của ma trận. Khi xác định giá trị của nó, họ thường dừng lại ở việc kiểm tra hai điều kiện:

||g|| =
hoặc || g|| =
, (1.14)

Ở đâu
. Sự hội tụ cũng được đảm bảo nếu ma trận ban đầu MỘT có ưu thế đường chéo, tức là

. (1.15)

Khi các điều kiện (1.14) hoặc (1.15) được thỏa mãn, phương pháp lặp hội tụ cho bất kỳ xấp xỉ ban đầu nào
. Vectơ thường xuyên nhất
lấy số 0 hoặc đơn vị hoặc chính vectơ từ hệ (1.13).

Nếu điều kiện (1.15) được thỏa mãn, thì việc chuyển đổi sang dạng lặp (1.13) có thể được thực hiện đơn giản bằng cách giải từng Tôi-phương trình thứ của hệ thống (1) đối với x Tôi theo các công thức đệ quy sau:

g ij = − Một ij / Một ii ; g ii = 0; f Tôi = b Tôi / Một ii , (1.15*)

I E.
.

Nếu trong ma trận MỘT không có ưu thế đường chéo, nó phải đạt được thông qua một số phép biến đổi tuyến tính không vi phạm tính tương đương của chúng.

Cuộc hẹn. Dịch vụ này nhằm giải quyết các vấn đề lập trình động bằng cách sử dụng các phương pháp quét tiến và lùi trong chế độ trực tuyến (xem ví dụ về giải quyết vấn đề phân phối đầu tư tối ưu).

Chỉ dẫn. Chọn số đối tượng và số nhóm tùy chọn, nhấn Next. Trong cửa sổ mới chọn phương pháp quét.

Số đối tượng 2 3 4 5 6 7 8 9 10 Số tùy chọn 2 3 4 5 6 7 8 9 10

Ví dụ 1. Giải bài toán bằng phương pháp quy hoạch động theo thời gian tiến và lùi đối với hàm mục tiêu cho trong bảng.
F(x 1 ,x 2 ,x 3) = f 1 (x 1) + f 2 (x 2) + f 3 (x 3) → cực đại
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

Giải pháp.
Tôi sân khấu. tối ưu hóa có điều kiện. f 1 (L) = max(f 1); 0 ≤ x 1 ≤ 5; x 1 \u003d 0.1.2.3.4.5.
f 1 (0) = cực đại = 6
f 1 (1) = cực đại = 7
f 1 (2) = cực đại = 11
f 1 (3) = cực đại = 12
f 1 (4) = cực đại = 15
f 1 (5) = cực đại = 16
Bảng 1 - Tính giá trị của hàm 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) = cực đại; 0 ≤ x 2 ≤ 5; x 2 \u003d 0.1.2.3.4.5.
f 2 (0) = cực đại = 15
f 2 (1) = cực đại = 16
f 2 (2) = cực đại = 20
f 2 (3) = cực đại = 21
f 2 (4) = cực đại = 24
f 2 (5) = cực đại = 25
Bảng 2 - Tính giá trị của hàm f 2 (L)

L	0	1	2	3	4	5
f 2 (L)	15	16	20	21	24	25
x2	0	0	0	0	0	0

f 3 (L) = cực đại; 0 ≤ x 3 ≤ 5; x 3 \u003d 0.1.2.3.4.5.
f 3 (0) = cực đại = 23
f 3 (1) = cực đại = 24
f 3 (2) = cực đại = 28
f 3 (3) = cực đại = 29
f 3 (4) = cực đại = 32
f 3 (5) = cực đại = 33
Bảng 3 - Tính giá trị của hàm 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

Giai đoạn II. tối ưu hóa vô điều kiện.
Như vậy, cực đại f 3 (5) = 33
Trong trường hợp này, x 3 \u003d 0, vì f 3 (5) \u003d 33 đạt được tại x 3 \u003d 0 (xem bảng 3).
Số x còn lại được phân phối như sau:
L=5 - 2*0=5
f 2 (5) = 25 đạt được tại x 2 = 0 (xem bảng 2).
L=5 - 2*0=5
f 1 (5) = 16 đạt được tại x 1 = 5 (xem bảng 1).
L=5 - 1*5=0
Kết quả là, tùy chọn tốt nhất đạt được với các giá trị: x 1 = 5, x 2 = 0, x 3 = 0

Ví dụ #2. Xem xét bài toán phân bổ vốn tối ưu K = nh trong m quỹ độc lập khác nhau (ngân hàng, tổ chức, hãng, v.v.) mà lợi nhuận kỳ vọng f i đã biết cho các khoản đầu tư x i = ih, i = 1..n. Ở đây n là số lượng gia tăng rời rạc h (rời rạc) mà tư bản K được chia.
Giả sử dữ liệu đó có sẵn cho bốn quỹ (m=4) với h = 1 triệu rúp, n = 6

Giải pháp.
Tôi sân khấu. Tối ưu hóa có điều kiện.
Bước 1: k = 4.
Giả sử rằng tất cả các quỹ với số lượng x 4 = 6 được cấp cho doanh nghiệp thứ 4. Trong trường hợp này, thu nhập tối đa, như có thể thấy từ bảng 1*, sẽ là 0,56, do đó:
F 4 (c 4) \u003d g 4 (x 4)
Bảng 1.

0	x 1	0	1	2	3	4	5	6
x4	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

Bảng 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

Bước 2: k = 3.

F 3 (c 3) \u003d max [ g 3 (x 3) + F 4 (c 3 - x 3)]
Ban 2.

0	x2	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

Điền vào bảng 2*. Để làm điều này, trên mỗi đường chéo phía đông bắc, chúng tôi tìm số lớn nhất, chúng tôi đánh dấu bằng dấu hoa thị và cho biết giá trị tương ứng x 2.
Ban 2*.

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

Bước thứ 3: k=2.
Chúng tôi xác định chiến lược tối ưu để phân phối vốn giữa các doanh nghiệp khác. Trong trường hợp này, quan hệ truy hồi Bellman có dạng:
F 2 (c 2) \u003d max [g 2 (x 2) + F 3 (c 2 - x 2)]
bàn số 3

0	x 3	0	1	2	3	4	5	6
x2	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

Ta điền vào bảng 3*. Để làm điều này, trên mỗi đường chéo phía đông bắc, chúng tôi tìm số lớn nhất, chúng tôi đánh dấu bằng dấu hoa thị và cho biết giá trị tương ứng x 3 .
Bàn số 3*.

c3	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

Bước thứ 4: k = 1.
Chúng tôi xác định chiến lược tối ưu để phân phối vốn giữa các doanh nghiệp khác. Trong trường hợp này, quan hệ truy hồi Bellman có dạng:
F 1 (c 1) \u003d max [ g 1 (x 1) + F 2 (c 1 - x 1)]
Bảng 4

0	x4	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

Chúng tôi điền vào bảng 4 *. Để làm điều này, trên mỗi đường chéo phía đông bắc, chúng tôi tìm số lớn nhất, chúng tôi đánh dấu bằng dấu hoa thị và cho biết giá trị tương ứng x 4 .
Bảng 4*.

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

Giai đoạn II. Tối ưu hóa vô điều kiện.
Bước 1: k = 1.
Theo Bảng 4*, thu nhập tối đa khi 6 được phân phối giữa các doanh nghiệp là c 1 = 6, F 1 (6) = 1,26. Trong trường hợp này, doanh nghiệp thứ 1 cần phân bổ x 1 = 3.
Bước 2: k = 2.

c 2 \u003d c 1 - x 1 \u003d 6 - 3 \u003d 3.
Theo bảng 3*, thu nhập tối đa khi 3 được phân phối giữa các doanh nghiệp là c 2 = 3, F 2 (3) = 0,61. Trong trường hợp này, doanh nghiệp thứ 2 cần phân bổ x 2 = 2.
Bước thứ 3: k = 3.
Hãy để chúng tôi xác định số tiền còn lại do phần của các doanh nghiệp khác.
c 3 \u003d c 2 - x 2 \u003d 3 - 2 \u003d 1.
Theo Bảng 2*, thu nhập tối đa khi 1 được phân phối giữa các doanh nghiệp là c 3 = 1, F 3 (1) = 0,2. Trong trường hợp này, doanh nghiệp thứ 3 cần phân bổ x 3 \u003d 0.
Bước thứ 4: k=4.
Hãy để chúng tôi xác định số tiền còn lại do phần của các doanh nghiệp khác.
c 4 \u003d c 3 - x 3 \u003d 1 - 0 \u003d 1.
Theo Bảng 1*, thu nhập tối đa khi 1 được phân phối giữa các doanh nghiệp là c 4 = 1, F 4 (1) = 0,20. Trong trường hợp này, doanh nghiệp thứ 4 cần phân bổ x 4 \u003d 1.
Như vậy, phương án đầu tư tối ưu cho doanh nghiệp:
x 1 = 3
x2 = 2
x 3 = 0
x4 = 1
sẽ mang lại thu nhập tối đa bằng: F(6) = g 1 (3) + g 2 (2) + g 3 (0) + g 4 (1) = 0,65 + 0,41 + 0 + 0,20 = 1,26.

Thuật toán đơn giản nhất để tính nghiệm chênh lệch là dành cho các mạch tường minh. Tuy nhiên, các phương pháp rõ ràng chỉ ổn định theo các tỷ lệ nhất định giữa các bước lưới. Việc đáp ứng các yêu cầu về độ ổn định dẫn đến nhu cầu về sự rời rạc hóa của biến thời gian, làm tăng thời gian tính toán.

Các sơ đồ ẩn, như một quy luật, không có thiếu sót này và cho phép lựa chọn độc lập các bước lưới theo thời gian và không gian. Tuy nhiên, trên mỗi lớp thời gian (lặp), cần giải một hệ phương trình đại số có số ẩn số bằng số nút trên lớp đang xét. Nếu chúng ta không tính đến các tính năng của hệ thống này (độ thưa thớt của ma trận) và giải quyết nó như một hệ thống chung, thì sẽ cần một số lượng đáng kể các phép toán số học.

Một phương pháp hiệu quả để giải các hệ phương trình được tạo bởi các lược đồ sai phân là phương thức chạy. Hãy xem xét thuật toán của nó bằng cách sử dụng giải pháp chênh lệch của bài toán giá trị biên đầu tiên cho phương trình nhiệt làm ví dụ. Đối với bài toán giá trị biên trong diện tích hình chữ nhật

xem xét sơ đồ khác biệt ngầm

Đây Ai = Ci = 1, bí = 1 + /?. 2 /(2at), D = li 2 (-u"- g / ") / (2at). Trong trường hợp của chúng tôi MỘT j, D và C* không phụ thuộc vào chỉ số Tôi, tuy nhiên, nếu bước lưới là biến, thì tất cả các hệ số sẽ phụ thuộc vào số nút. Điều quan trọng cần lưu ý là А(, Bj, Ci, g n+l , / n+1 - giá trị đã biết. Hệ thức (7.2) là một hệ phương trình tuyến tính cho các ẩn số Uq + , Mg + .

Ma trận khai triển của hệ này có dạng

Trong ma trận này, các phần tử khác không nằm dọc theo đường chéo chính và hai phần tử lân cận. Loại ma trận này được gọi là tam giác.

Sự hiện diện của điều kiện biên bên trái (mq +1 = n+1) cho phép tìm kiếm nghiệm ở dạng (để đơn giản trong ký hiệu, chỉ số trên của ẩn số được bỏ qua) như

Nó được gọi là tỷ lệ quét, và các hệ số A"*_i được bao gồm trong đó và Li- - hệ số quét. Vì tôi = 1 (7.1) được thỏa mãn nếu chúng tôi chấp nhận

Do đó, các giá trị ban đầu của các hệ số đua được thiết lập.

Sử dụng quan hệ lũy tiến (7.3), chúng tôi loại bỏ các ẩn số sch-1 từ (7.2):

Sau khi thực hiện các phép biến đổi toán học đơn giản nhất, chúng ta thu được

trong một hình thức trùng với tỷ lệ quét. So sánh (7.5) và (7.3) đưa ra quan hệ truy hồi cho các hệ số quét:

Sử dụng các giá trị ban đầu đồng = 0, Lq = , ta có thể tính tuần tự K, L], ĐẾN2 , ^2, ..., Ln- thành phần vectơ của hệ số quét. Quá trình tính toán này được gọi là chạy thẳng. Dễ dàng nhận thấy rằng một phép quét trực tiếp sử dụng các phép biến đổi cơ bản sẽ biến đổi ma trận tam giác của hệ thống tuyến tính ban đầu thành ma trận hai đường chéo trên và số lượng các phép tính số học (do dạng đặc biệt của ma trận gốc) tỷ lệ thuận với số ẩn số 1 .

Dạng hai đường chéo của ma trận kết quả giúp dễ dàng xây dựng quy trình tính toán các ẩn số. Quan hệ quét cho nút cuối cùng wjv-i = Kn-Un + l^~ 1, cùng với điều kiện biên phải = tôi, cho phép chúng tôi tính idr_ 1, sau đó, sử dụng công thức đệ quy (7.3), lần lượt xác định tất cả các ẩn số không-2, un-3, ..., sch vấn đề khác biệt. Phép tính tuần tự các ẩn số sử dụng quan hệ quét (7.3) được gọi là chạy ngược lại. Về cốt lõi, phương pháp quét là một biến thể của phép loại bỏ Gaussian, có tính đến các đặc thù của cấu trúc của ma trận tam giác và loại bỏ các phép toán trên các phần tử 0 của nó.

Dễ dàng nhận thấy rằng khi giải một hệ phương trình tuyến tính có ma trận tam giác bằng phương pháp quét thì số phép tính tỷ lệ thuận với số nút của lưới sai phân nên việc sử dụng phương pháp quét cho phép ta xây dựng chương trình chênh lệch kinh tế.

Một trường hợp quan trọng khác, bằng chứng có thể được tìm thấy trong tài liệu chuyên ngành, là tính ổn định tính toán của phương pháp quét. Điều này có nghĩa là độ chính xác của giải pháp thu được sẽ giống như độ chính xác của các phép tính trung gian.

Phương pháp quét lần đầu tiên được đề xuất bởi các nhà toán học Liên Xô Gelfond và Lokutsievskii vào những năm 1950 để giải quyết các vấn đề về giá trị biên. Hiệu quả và tính ổn định của phương pháp đã có lúc khiến nó trở thành yếu tố chính trong giải pháp cho các sơ đồ khác biệt tiềm ẩn. Việc áp dụng các ý tưởng phân tách đối với các biến không gian giúp mở rộng các thuật toán dựa trên prog cho lớp các vấn đề đa chiều. Trong những năm gần đây, do sự phát triển nhanh chóng của tài nguyên công nghệ máy tính (chủ yếu là RAM), các thuật toán khác để giải các hệ đại số nhiều chiều với ma trận thưa thớt đã được sử dụng rộng rãi, không giống như phương pháp quét, không bị ràng buộc bởi một quy tắc nghiêm ngặt như vậy. yêu cầu là tam giác.

• Sai lệch so với tính hai đường chéo của biến cuối cùng trong trường hợp điều kiện biên loại thứ hai hoặc thứ ba có thể dễ dàng khắc phục.
• Điều kiện ổn định được thỏa mãn nếu ma trận có tính chất thống trị đường chéo. Thuộc tính này đúng cho các ma trận được tạo bởi các sơ đồ khác biệt của lớp đang được xem xét.