Giải hệ phương trình bằng phép lặp đơn giản. Giải pháp Slough bằng cách lặp lại đơn giản

Chủ đề 3. Giải pháp của hệ thống tuyến tính phương trình đại số các phương pháp lặp.

Các phương pháp trực tiếp để giải SLAE được mô tả ở trên không hiệu quả lắm khi giải quyết các hệ thống quy mô lớn (tức là khi giá trị N đủ lớn). Trong những trường hợp như vậy, các phương pháp lặp lại phù hợp hơn để giải quyết các SLAE.

Các phương pháp lặp lại để giải SLAE(tên thứ hai của chúng là các phương thức xấp xỉ liên tiếp giải pháp) không đưa ra lời giải chính xác của SLAE, mà chỉ đưa ra giá trị gần đúng cho lời giải và mỗi ước lượng tiếp theođược lấy từ cái trước và chính xác hơn cái trước (với điều kiện là sự hội tụ lần lặp). Giá trị xấp xỉ ban đầu (hay còn gọi là không) được chọn gần với lời giải được đề xuất hoặc tùy ý (nó có thể được coi là vectơ của vế phải của hệ thống). Lời giải chính xác được tìm thấy là giới hạn của các phép gần đúng vì số của chúng có xu hướng đến vô cùng. Như một quy luật, đối với số giới hạn số bước (tức là số lần lặp lại) không đạt đến giới hạn này. Do đó, trong thực tế, khái niệm độ chính xác của giải pháp cụ thể là một số tích cực và đủ nhỏ e và quá trình tính toán (lặp lại) được thực hiện cho đến khi hoàn thành mối quan hệ .

Đây là giá trị gần đúng với giải pháp thu được sau số lần lặp N , và là giải pháp chính xác của SLAE (không được biết trước). Số lần lặp lại N = N (e ) cần thiết để đạt được độ chính xác được chỉ định cho các phương pháp cụ thể có thể thu được từ những cân nhắc lý thuyết (tức là có công thức tính toán). Chất lượng của các phương pháp lặp khác nhau có thể được so sánh bằng số lần lặp cần thiết để đạt được độ chính xác như nhau.

Để nghiên cứu các phương pháp lặp lại trên sự hội tụ bạn cần có khả năng tính toán các chỉ tiêu của ma trận. Chuẩn ma trận- đây là một số giá trị số, đặc trưng cho độ lớn của các phần tử ma trận theo giá trị tuyệt đối. TẠI toán học cao hơn có một số các loạiđịnh mức ma trận, thường là tương đương. Trong khóa học của chúng tôi, chúng tôi sẽ chỉ sử dụng một trong số chúng. Cụ thể, dưới tiêu chuẩn ma trận chúng tôi sẽ hiểu giá trị lớn nhất trong số các tổng giá trị tuyệt đối của các phần tử của các hàng riêng lẻ của ma trận. Để chỉ định chuẩn của một ma trận, tên của nó bao gồm hai cặp dấu gạch ngang dọc. Vì vậy, đối với ma trận Một theo tiêu chuẩn của nó, chúng tôi có nghĩa là số lượng

. (3.1)

Vì vậy, ví dụ, chuẩn của ma trận A từ ví dụ 1 như sau:

Được sử dụng rộng rãi nhất để giải SLAE là ba phương pháp lặp lại

Phương pháp lặp lại đơn giản

Phương pháp Jacobi

Phương pháp Guass-Seidel.

Phương pháp lặp lại đơn giản liên quan đến việc chuyển đổi từ viết SLAE ở dạng ban đầu (2.1) sang viết nó ở dạng

(3.2)

hoặc, cũng là dạng ma trận,

x = TỪ × x + D , (3.3)

C - ma trận các hệ số của hệ thống các chiều được biến đổi N ´ N

x - vectơ của ẩn số, bao gồm N thành phần

D - vectơ của các phần bên phải của hệ thống đã biến đổi, bao gồm N thành phần.

Hệ thống ở dạng (3.2) có thể được biểu diễn dưới dạng viết tắt

Từ cái nhìn này công thức lặp đơn giản sẽ trông như thế nào

ở đâu m - số lần lặp và - giá trị xj trên m -bước lặp thứ. Sau đó, nếu quá trình lặp lại hội tụ, với sự gia tăng số lần lặp lại, sẽ có

Chứng minh rằng quá trình lặp lại hội tụ, nếu định mức ma trận D sẽ là ít hơn đơn vịS.

Nếu chúng ta lấy vectơ của các số hạng tự do làm xấp xỉ ban đầu (không), tức là x (0) = D , sau đó biên độ của lỗi có hình thức

(3.5)

dưới đây x * là giải pháp chính xác của hệ thống. Do đó,

nếu , sau đó bởi đưa ra độ chính xáce có thể được tính toán trước số lần lặp lại cần thiết. Cụ thể, từ mối quan hệ

sau những biến đổi nhẹ, chúng tôi nhận được

. (3.6)

Khi thực hiện một số lần lặp lại như vậy, đảm bảo độ chính xác đã cho của việc tìm lời giải cho hệ thống được đảm bảo. Ước tính lý thuyết này khối lượng bắt buộc các bước lặp lại hơi đắt. Trong thực tế, độ chính xác cần thiết có thể đạt được với số lần lặp lại ít hơn.

Thật thuận tiện khi tìm kiếm các giải pháp cho một SLAE nhất định bằng phương pháp lặp lại đơn giản với việc nhập kết quả thu được vào một bảng có dạng sau:

	x 1	x 2		x n

Cần đặc biệt lưu ý rằng khi giải quyết SLAE bằng phương pháp này khó khăn và gian khổ nhất là biến đổi hệ thống từ dạng (2.1) sang dạng (3.2). Các phép biến đổi này phải tương đương, tức là điều đó không làm thay đổi nghiệm của hệ thống ban đầu và đảm bảo giá trị của định mức của ma trận C (sau khi thực hiện chúng) ít hơn một. Không có công thức duy nhất cho các phép biến đổi như vậy. Ở đây trong mỗi trường hợp cần thể hiện sự sáng tạo. Xem xét ví dụ, trong đó một số cách chuyển đổi hệ thống sang dạng yêu cầu sẽ được đưa ra.

ví dụ 1 Hãy để chúng tôi tìm nghiệm của hệ phương trình đại số tuyến tính bằng phương pháp lặp đơn giản (với độ chính xác e= 0.001)

Hệ thống này được giảm xuống dạng yêu cầu theo cách đơn giản nhất. Chúng tôi chuyển tất cả các số hạng từ vế trái sang vế phải, rồi thêm vào cả hai vế của mỗi phương trình x tôi (tôi = 1, 2, 3, 4). Chúng tôi nhận được một hệ thống đã biến đổi có dạng sau

.

Ma trận C và vectơ D trong trường hợp này sẽ như sau

C = , D = .

Tính định mức ma trận C . Lấy

Vì tiêu chuẩn hóa ra nhỏ hơn một, nên sự hội tụ của phương pháp lặp đơn giản được đảm bảo. Là xấp xỉ ban đầu (không), chúng tôi lấy các thành phần của vectơ D . Lấy

, , , .

Sử dụng công thức (3.6), chúng tôi tính số bước lặp cần thiết. Đầu tiên chúng ta hãy xác định chuẩn của vectơ D . Lấy

.

Vì vậy, để đạt được độ chính xác quy định, cần thực hiện ít nhất 17 lần lặp. Hãy thực hiện lần lặp đầu tiên. Lấy

Sau khi thực hiện tất cả các phép toán số học, chúng tôi nhận được

.

Tiếp tục theo cách tương tự, chúng tôi thực hiện các bước lặp tiếp theo. Kết quả của họ được tóm tắt trong bảng sau ( D - giá trị lớn nhất thành phần giải pháp thay đổi giữa các bước hiện tại và trước đó)

M

Vì sau bước thứ mười, sự khác biệt giữa các giá trị ở hai lần lặp cuối cùng đã trở nên nhỏ hơn độ chính xác được chỉ định, quá trình lặp sẽ bị chấm dứt. Là giải pháp tìm thấy, chúng tôi lấy các giá trị thu được ở bước cuối cùng.

Ví dụ 2

Hãy làm tương tự như trong ví dụ trước. Lấy

Ma trận C một hệ thống như vậy sẽ

C =.

Hãy tính định mức của nó. Lấy

Rõ ràng, quá trình lặp lại cho một ma trận như vậy sẽ không hội tụ. Cần tìm một cách khác để biến đổi hệ phương trình đã cho.

Hãy sắp xếp lại các phương trình riêng của nó trong hệ phương trình ban đầu để dòng thứ ba trở thành dòng thứ nhất, dòng thứ nhất - dòng thứ hai, dòng thứ hai - dòng thứ ba. Sau đó, chuyển đổi nó theo cách tương tự, chúng tôi nhận được

Ma trận C một hệ thống như vậy sẽ

C =.

Hãy tính định mức của nó. Lấy

Kể từ khi định mức ma trận C hóa ra nhỏ hơn sự thống nhất, do đó hệ thống được biến đổi phù hợp để giải bằng phép lặp đơn giản.

Ví dụ 3 Ta biến đổi hệ phương trình

sang một dạng cho phép sử dụng phương pháp lặp đơn giản khi giải nó.

Đầu tiên chúng ta hãy tiến hành tương tự như ví dụ 1. Chúng ta thu được

Ma trận C một hệ thống như vậy sẽ

C =.

Hãy tính định mức của nó. Lấy

Rõ ràng, quá trình lặp lại cho một ma trận như vậy sẽ không hội tụ.

Để biến đổi ma trận ban đầu về dạng thuận tiện cho việc áp dụng phương pháp lặp đơn giản, ta tiến hành như sau. Đầu tiên, chúng tôi hình thành một hệ phương trình "trung gian" trong đó

- phương trình đầu tiên là tổng của phương trình thứ nhất và thứ hai của hệ ban đầu

- phương trình thứ hai- tổng của phương trình thứ ba nhân đôi với phương trình thứ hai trừ đi phương trình thứ nhất

- phương trình thứ ba- sự khác biệt giữa phương trình thứ ba và thứ hai của hệ thống ban đầu.

Kết quả là chúng ta thu được một hệ phương trình tương đương với hệ phương trình "trung gian" ban đầu

Từ đó có thể dễ dàng có được một hệ thống khác, một hệ thống "trung gian"

,

và từ nó chuyển đổi

.

Ma trận C một hệ thống như vậy sẽ

C =.

Hãy tính định mức của nó. Lấy

Quá trình lặp lại cho một ma trận như vậy sẽ là hội tụ.

Phương pháp Jacobi giả định rằng tất cả các phần tử đường chéo của ma trận Một của hệ thống ban đầu (2.2) không bằng không. Sau đó, hệ thống ban đầu có thể được viết lại thành

(3.7)

Từ bản ghi như vậy, hệ thống được hình thành công thức lặp lại Phương pháp Jacobi

Điều kiện để có sự hội tụ của quá trình lặp lại của phương pháp Jacobi là cái gọi là điều kiện thống trị đường chéo trong hệ thống ban đầu (có dạng (2.1)). Về mặt phân tích, điều kiện này được viết là

. (3.9)

Cần lưu ý rằng nếu trong hệ thống nhất định phương trình, điều kiện hội tụ của phương pháp Jacobi (tức là điều kiện thống trị đường chéo) không được thỏa mãn, trong nhiều trường hợp có thể bằng phép biến đổi tương đương SLAE ban đầu để đưa giải pháp của nó thành giải pháp của SLAE tương đương trong đó điều kiện này được thỏa mãn.

Ví dụ 4 Ta biến đổi hệ phương trình

sang một dạng cho phép sử dụng phương pháp Jacobi để giải nó.

Chúng ta đã xem xét hệ này trong Ví dụ 3, vì vậy chúng ta sẽ chuyển từ nó sang hệ phương trình “trung gian” thu được ở đó. Dễ dàng thiết lập rằng điều kiện ưu thế đường chéo được thỏa mãn đối với nó, vì vậy chúng tôi biến đổi nó thành dạng cần thiết để áp dụng phương pháp Jacobi. Lấy

Từ đó, chúng tôi có được một công thức để thực hiện các phép tính bằng phương pháp Jacobi cho một SLAE nhất định

Như ban đầu, tức là bằng không, xấp xỉ vector của các số hạng tự do sẽ thực hiện tất cả các phép tính cần thiết. Chúng tôi tóm tắt kết quả trong một bảng

m					D

Đầy đủ độ chính xác cao giải pháp thu được đã đạt được trong sáu lần lặp lại.

Phương pháp Gauss-Seidel là một cải tiến của phương pháp Jacobi và cũng giả định rằng tất cả các phần tử đường chéo của ma trận Một của hệ thống ban đầu (2.2) không bằng không. Sau đó, hệ thống ban đầu có thể được viết lại theo một hình thức tương tự như phương pháp Jacobi, nhưng hơi khác so với nó

Điều quan trọng cần nhớ ở đây là nếu chỉ số trên trong dấu tổng kết nhỏ hơn chỉ số dưới, thì không có phép tổng kết nào được thực hiện.

Ý tưởng của phương pháp Gauss-Seidel nằm ở chỗ các tác giả của phương pháp này đã nhìn thấy khả năng tăng tốc quá trình tính toán so với phương pháp Jacobi do thực tế là trong quá trình lặp tiếp theo, đã tìm thấy một giá trị mới x 1 có thể Một lần sử dụng giá trị mới này trong cùng một lần lặp lạiđể tính toán phần còn lại của các biến. Tương tự, xa hơn, việc tìm kiếm một giá trị mới x 2 bạn cũng có thể sử dụng nó ngay lập tức trong cùng một lần lặp lại, v.v.

Dựa vào cái này, công thức lặp cho phương pháp Gauss-Seidel Nó có lần xem tiếp theo

Đủ chođiều kiện hội tụ quá trình lặp đi lặp lại của phương pháp Gauss-Seidel vẫn ở cùng một điều kiện thống trị đường chéo (3.9). Tỷ lệ hội tụ phương pháp này cao hơn một chút so với phương pháp Jacobi.

Ví dụ 5 Chúng tôi giải hệ phương trình bằng phương pháp Gauss-Seidel

Chúng ta đã xem xét hệ này trong Ví dụ 3 và 4, vì vậy chúng ta sẽ ngay lập tức chuyển từ nó sang hệ phương trình đã biến đổi (xem Ví dụ 4), trong đó điều kiện thống trị về đường chéo được thỏa mãn. Từ đó, chúng tôi có được một công thức để thực hiện các phép tính bằng phương pháp Gauss-Seidel

Lấy vectơ của các số hạng tự do làm xấp xỉ ban đầu (tức là không), chúng tôi thực hiện tất cả các phép tính cần thiết. Chúng tôi tóm tắt kết quả trong một bảng

m

Độ chính xác khá cao của giải pháp thu được đã đạt được trong năm lần lặp lại.

Ưu điểm của phương pháp lặp lại là khả năng áp dụng cho các hệ thống có điều kiện thấp và các hệ thống có yêu cầu cao, khả năng tự điều chỉnh và dễ thực hiện trên PC. Các phương pháp lặp đi lặp lại để bắt đầu tính toán yêu cầu một số xấp xỉ ban đầu với 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 thuộc tính của ma trận NHƯNG hệ thống và sự lựa chọn các giá trị gần đúng ban đầu.

Để áp dụng phương pháp lặp, hệ thống ban đầu (2.1) hoặc (2.2) phải được rút gọn về dạng

sau đó quá trình lặp lại được thực hiện theo công thức lặp lại

, k = 0, 1, 2, ... . (2.26một)

Ma trận G và vectơ thu được là kết quả của phép biến đổi hệ (2.1).

Đối với sự hội tụ (2,26 một) là cần thiết và đủ cho | l tôi(G)| < 1, где ltôi(G) - tất cả các giá trị riêng ma trận G. Sự hội tụ cũng sẽ xảy ra nếu || G|| < 1, так как |ltôi(G)| < " ||G||, ở đâu "là bất kỳ.

Biểu tượng || ... || 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|| = , (2.27)

ở đâu . Sự hội tụ cũng được đảm bảo nếu ma trận ban đầu NHƯNG có ưu thế về đường chéo, tức là

. (2.28)

Nếu (2.27) hoặc (2.28) được thỏa mãn, phương pháp lặp hội tụ cho bất kỳ giá trị gần đúng ban đầu nào. Thông thường, vectơ được coi là không hoặc đơn nhất, hoặc chính vectơ được lấy từ (2.26).

Có nhiều cách tiếp cận để biến đổi hệ thống ban đầu (2.2) với ma trận NHƯNGđảm bảo dạng (2.26) hoặc thỏa mãn điều kiện hội tụ (2.27) và (2.28).

Ví dụ, (2.26) có thể nhận được như sau.

Để cho NHƯNG = TẠI+ TỪ, det TẠI¹ 0; sau đó ( B+ TỪ)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1, khi nào = - B –1 C+ B –1 .

Đặt - B –1 C = G, B–1 =, ta thu được (2.26).

Từ các điều kiện hội tụ (2.27) và (2.28) được thấy rằng biểu diễn NHƯNG = TẠI+ TỪ không thể tùy tiện.

Nếu ma trận NHƯNG thỏa mãn điều kiện (2.28) thì dưới dạng ma trận TẠI bạn có thể chọn hình tam giác dưới:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Bằng cách chọn tham số a, chúng ta có thể đảm bảo rằng || G|| = ||E+ a Một|| < 1.

Nếu (2.28) chiếm ưu thế, thì việc chuyển đổi thành (2.26) có thể được thực hiện bằng cách giải từng tôi phương trình thứ của hệ (2.1) đối với x tôi theo các công thức đệ quy sau:

(2.28một)

Nếu trong ma trận NHƯNG không có sự thống trị theo đường chéo, nó phải đạt được với sự giúp đỡ của một số biến đổi tuyến tínhđiều đó không vi phạm tính tương đương của chúng.

Ví dụ, hãy xem xét hệ thống

(2.29)

Như có thể thấy, trong phương trình (1) và (2) không có sự thống trị của đường chéo, nhưng ở (3) thì có, vì vậy chúng ta giữ nguyên.

Hãy để chúng tôi đạt được ưu thế về đường chéo trong phương trình (1). Nhân (1) với a, (2) với b, cộng cả hai phương trình và chọn a và b trong phương trình kết quả sao cho có ưu thế về đường chéo:

(2a + 3b) X 1 + (-1,8a + 2b) X 2 + (0,4a - 1,1b) X 3 = a.

Lấy a = b = 5, ta được 25 X 1 + X 2 – 3,5X 3 = 5.

Để biến đổi phương trình (2) với ưu thế (1), chúng ta nhân với g, (2) chúng ta nhân với d, và trừ (1) với (2). Lấy

(3d - 2g) X 1+ (2d + 1,8g) X 2 + (- 1,1 ngày - 0,4g) X 3 = −g.

Đặt d = 2, g = 3, ta được 0 X 1 + 9,4 X 2 – 3,4 X 3 = -3. Kết quả là, chúng tôi nhận được hệ thống

(2.30)

Kỹ thuật này có thể được sử dụng để tìm lời giải cho nhiều loại ma trận.

hoặc

Lấy gần đúng ban đầu, vectơ = (0,2; -0,32; 0) T, chúng tôi sẽ giải quyết hệ thống này bằng công nghệ (2,26 một):

k = 0, 1, 2, ... .

Quá trình tính toán dừng lại khi hai xấp xỉ lân cận của vectơ nghiệm trùng khớp về độ chính xác, tức là

.

Công nghệ giải pháp lặp đi lặp lại tử tế (2,26 một) được đặt tên bằng cách lặp lại đơn giản .

Lớp lỗi tuyệt đốiđối với phương pháp lặp lại đơn giản:

ký hiệu ở đâu || ... || có nghĩa là chuẩn mực.

Ví dụ 2.1. Sử dụng phương pháp lặp đơn giản với độ chính xác e = 0,001, giải hệ Các phương trình tuyến tính:

Số bước đưa ra câu trả lời chính xác với e = 0,001 có thể được xác định từ quan hệ

0,001 bảng Anh.

Chúng ta hãy ước lượng độ hội tụ theo công thức (2.27). Đây || G|| = = max (0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Như một phép gần đúng ban đầu, chúng tôi lấy vectơ của các số hạng tự do, tức là = (2,15; -0,83; 1,16; 0,44) T. Chúng tôi thay thế các giá trị của vectơ thành (2,26 một):

Tiếp tục tính toán, chúng ta sẽ nhập kết quả vào bảng:

k	X 1	X 2	X 3	X 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Sự hội tụ tính bằng phần nghìn đã diễn ra ở bước thứ 10.

Câu trả lời: X 1 »3,571; X 2 »-0,957; X 3 »1.489; X 4 "-0,836.

Giải pháp này cũng có thể thu được bằng cách sử dụng các công thức (2.28 một).

Ví dụ 2.2. Để minh họa thuật toán bằng công thức (2.28 một) xem xét giải pháp của hệ thống (chỉ có hai lần lặp lại):

; . (2.31)

Hãy biến đổi hệ thống thành dạng (2.26) theo (2.28 một):

Þ (2.32)

Hãy lấy ước lượng ban đầu = (0; 0; 0) T. Sau đó k= 0 rõ ràng giá trị = (0,5; 0,8; 1,5) T. Hãy để chúng tôi thay thế các giá trị này thành (2.32), nghĩa là k= 1 ta được = (1,075; 1,3; 1,175) T.

Lỗi e 2 = = max (0,575; 0,5; 0,325) = 0,575.

Sơ đồ khối của thuật toán tìm lời giải SLAE bằng phương pháp lặp lại đơn giản theo công thức làm việc (2,28 một) được hiển thị trong Hình. 2.4.

Một tính năng của sơ đồ khối là sự hiện diện của các khối sau:

- khối 13 - mục đích của nó được thảo luận dưới đây;

- khối 21 - hiển thị kết quả trên màn hình;

- khối 22 - xác minh (chỉ báo) của sự hội tụ.

Hãy để chúng tôi phân tích sơ đồ được đề xuất trên ví dụ của hệ thống (2.31) ( N= 3, w = 1, e = 0,001):

= ; .

Khối 1. Nhập dữ liệu ban đầu Một, , chúng tôi, N: N= 3, w = 1, e = 0,001.

Chu kỳ I. Đặt các giá trị ban đầu của các vectơ x 0tôi và x tôi (tôi = 1, 2, 3).

Khối 5. Đặt lại bộ đếm số lần lặp.

Khối 6. Đặt lại bộ đếm lỗi hiện tại.

TẠI vòng lặp II thay đổi số hàng của ma trận NHƯNG và vectơ.

Chu kỳ II:tôi = 1: S = b 1 = 2 (khối 8).

Chuyển đến vòng lặp lồng nhau III, khối 9 - bộ đếm số cột ma trận NHƯNG: j = 1.

Khối 10: j = tôi, do đó, chúng tôi quay lại khối 9 và tăng j trên mỗi đơn vị: j = 2.

Ở khối 10 j ¹ tôi(2 ¹ 1) - đến khối 11.

Khối 11: S= 2 - (–1) × X 0 2 \ u003d 2 - (-1) × 0 \ u003d 2, chuyển đến khối 9, trong đó j tăng một: j = 3.

Ở khối 10, điều kiện j ¹ tôiđược thực thi, vì vậy hãy chuyển đến khối 11.

Khối 11: S= 2 - (–1) × X 0 3 \ u003d 2 - (-1) × 0 \ u003d 2, sau đó chúng ta chuyển đến khối 9, trong đó j tăng một ( j= 4). Nghĩa j hơn N (N= 3) - kết thúc vòng lặp và chuyển đến khối 12.

Khối 12: S = S / một 11 = 2 / 4 = 0,5.

Khối 13: w = 1; S = S + 0 = 0,5.

Khối 14: d = | x tôi – S | = | 1 – 0,5 | = 0,5.

Khối 15: x tôi = 0,5 (tôi = 1).

Khối 16. Kiểm tra tình trạng d > de: 0,5> 0, do đó, chuyển đến khối 17, trong đó chúng tôi chỉ định de= 0,5 và trả về bằng tham chiếu " NHƯNG»Sang bước tiếp theo của chu kỳ II - đến khối 7, trong đó tôi tăng một.

Chu kỳ II: tôi = 2: S = b 2 = 4 (khối 8).

j = 1.

Qua khối 10 j ¹ tôi(1 ¹ 2) - đến khối 11.

Khối 11: S= 4 - 1 × 0 = 4, chuyển đến khối 9, trong đó j tăng một: j = 2.

Ở khối 10, điều kiện không đạt nên chúng tôi chuyển sang khối 9, trong đó j tăng một: j= 3. Bằng phép loại suy, chúng ta vượt qua khối 11.

Khối 11: S= 4 - (–2) × 0 = 4, sau đó ta kết thúc chu kỳ III và chuyển sang khối 12.

Khối 12: S = S/ một 22 = 4 / 5 = 0,8.

Khối 13: w = 1; S = S + 0 = 0,8.

Khối 14: d = | 1 – 0,8 | = 0,2.

Khối 15: x tôi = 0,8 (tôi = 2).

Khối 16. Kiểm tra tình trạng d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «NHƯNG»Sang bước tiếp theo của chu kỳ II - đến khối7.

Chu kỳ II: tôi = 3: S = b 3 = 6 (khối 8).

Đi đến vòng lặp lồng nhau III, khối 9: j = 1.

Khối 11: S= 6 - 1 × 0 = 6, chuyển đến khối 9: j = 2.

Qua khối 10, chúng tôi tiến tới khối 11.

Khối 11: S= 6 - 1 × 0 = 6. Kết thúc chu kỳ III chuyển sang khối 12.

Khối 12: S = S/ một 33 = 6 / 4 = 1,5.

Khối 13: S = 1,5.

Khối 14: d = | 1 – 1,5 | = 0,5.

Khối 15: x tôi = 1,5 (tôi = 3).

Theo khối 16 (có tính đến tài liệu tham khảo " NHƯNG" và " TỪ”) Thoát khỏi chu kỳ II và đến khối 18.

Khối 18. Tăng số lần lặp lại nó = nó + 1 = 0 + 1 = 1.

Trong khối 19 và 20 của chu kỳ IV, chúng tôi thay thế các giá trị ban đầu X 0tôi giá trị nhận được x tôi (tôi = 1, 2, 3).

Khối 21. Chúng tôi in các giá trị trung gian của lần lặp hiện tại, trong trường hợp này: = (0,5; 0,8; 1,5)T, nó = 1; de = 0,5.

Chúng tôi chuyển sang chu kỳ II trên khối 7 và thực hiện các phép tính đã xem xét với giá trị ban đầu X 0tôi (tôi = 1, 2, 3).

Sau đó chúng tôi nhận được X 1 = 1,075; X 2 = 1,3; X 3 = 1,175.

Tại đây, phương pháp Seidel hội tụ.

Theo công thức (2.33)

k	X 1	X 2	X 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Câu trả lời: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.

Bình luận. Nếu đối với cùng một hệ thống, phương pháp lặp đơn giản và phương pháp Seidel hội tụ, thì phương pháp Seidel sẽ thích hợp hơn. Tuy nhiên, trên thực tế, vùng hội tụ của các phương pháp này có thể khác nhau, tức là phương pháp lặp đơn giản hội tụ, trong khi phương pháp Seidel phân kỳ và ngược lại. Đối với cả hai phương pháp, nếu || G|| gần với đơn vị, tỷ lệ hội tụ rất thấp.

Để tăng tốc độ hội tụ, một kỹ thuật nhân tạo được sử dụng - cái gọi là phương pháp thư giãn . Bản chất của nó nằm ở chỗ giá trị tiếp theo thu được bằng phương pháp lặp x tôi (k) được tính toán lại theo công thức

trong đó w thường được thay đổi từ 0 thành 2 (0< w £ 2) с каким-либо шагом (h= 0,1 hoặc 0,2). Tham số w được chọn sao cho sự hội tụ của phương thức đạt được với số lần lặp tối thiểu.

Thư giãn- sự suy yếu dần dần của bất kỳ trạng thái nào của cơ thể sau khi các yếu tố gây ra trạng thái này ngừng hoạt động (vật lý. kỹ thuật.).

Ví dụ 2.4. Xem xét kết quả của lần lặp thứ năm bằng cách sử dụng công thức thư giãn. Hãy lấy w = 1,5:

Như bạn có thể thấy, kết quả của gần như lần lặp thứ bảy đã thu được.

GIỚI THIỆU

1. GIẢI PHÁP CHẬM BẰNG PHƯƠNG PHÁP ĐIỀU KHIỂN ĐƠN GIẢN

1.1 Mô tả phương pháp giải

1.2 Cơ sở

1.3 Thuật toán

1.4 Chương trình QBasic

1.5 Kết quả của chương trình

1.6 Kiểm tra kết quả của chương trình

2. TÁI TẠO ROOT BẰNG PHƯƠNG PHÁP TANGENT

2.1 Mô tả phương pháp giải

2.2 Dữ liệu ban đầu

2.3 Thuật toán

2.4 Chương trình QBasic

2.5 Kết quả của chương trình

2.6 Kiểm tra kết quả của chương trình

3. TÍCH HỢP SỐ THEO QUY TẮC PHẢN XẠ

3.1 Mô tả phương pháp giải

3.2 Dữ liệu ban đầu

3.3 Thuật toán

3.4 Chương trình QBasic

3.5 Kiểm tra kết quả của chương trình

4.1 Thông tin chung Về chương trình

4.1.1 Mục đích và tính năng đặc biệt

4.1.2 Hạn chế của WinRAR

4.1.3 Yêu cầu hệ thống WinRAR

4.2 Giao diện WinRAR

4.3 Chế độ quản lý tệp và lưu trữ

4.4 Sử dụng menu ngữ cảnh

PHẦN KẾT LUẬN

THƯ MỤC

GIỚI THIỆU

Đây hạn giấy là sự phát triển của các thuật toán và chương trình giải hệ phương trình đại số tuyến tính bằng phương pháp Gauss; phương trình phi tuyến sử dụng phương pháp hợp âm; vì hội nhập số theo quy tắc hình thang.

Phương trình đại số được gọi là phương trình chỉ chứa các hàm đại số (nguyên hàm, hữu tỉ, vô tỉ). Đặc biệt, đa thức là một hàm đại số toàn phần. Các phương trình chứa các hàm khác (lượng giác, hàm mũ, logarit và các hàm khác) được gọi là siêu nghiệm.

Các phương pháp giải hệ phương trình đại số tuyến tính được chia thành hai nhóm:

các phương pháp chính xác, là các thuật toán hữu hạn để tính toán gốc của một hệ thống (giải các hệ thống bằng cách sử dụng ma trận nghịch đảo, Quy tắc Cramer, phương pháp Gauss, v.v.),

· Các phương pháp lặp cho phép thu được một giải pháp của hệ thống với độ chính xác nhất định bằng các quy trình lặp hội tụ (phương pháp lặp, phương pháp Seidel, v.v.).

Do làm tròn không thể tránh khỏi, kết quả chẵn phương pháp chính xác là gần đúng. Hơn nữa, khi sử dụng phương thức lặp lại, lỗi của phương thức được thêm vào.

Giải hệ phương trình đại số tuyến tính là một trong những bài toán chính của đại số tuyến tính tính toán. Mặc dù vấn đề giải một hệ phương trình tuyến tính tương đối hiếm khi được quan tâm độc lập đối với các ứng dụng, nhưng khả năng giải các hệ đó thường phụ thuộc vào khả năng giải các hệ đó một cách hiệu quả. mô hình toán học nhiều quy trình có sự hỗ trợ của máy tính. Một phần quan trọng của các phương pháp số để giải các bài toán khác nhau (đặc biệt là phi tuyến tính) bao gồm giải hệ phương trình tuyến tính như một bước cơ bản của thuật toán tương ứng.

Để hệ phương trình đại số tuyến tính có nghiệm thì cần và đủ hạng của ma trận chính là ngang hàng ma trận mở rộng. Nếu hạng của ma trận chính bằng hạng của ma trận mở rộng và bằng số chưa biết, thì hệ thống có một giải pháp duy nhất. Nếu hạng của ma trận chính bằng hạng của ma trận mở rộng, nhưng số nhỏ hơn chưa biết thì hệ có vô số nghiệm.

Một trong những phương pháp phổ biến nhất để giải hệ phương trình tuyến tính là phương pháp Gauss. Phương pháp này được biết đến trong Các tùy chọn khác nhau trong hơn 2000 năm. Phương pháp Gauss là một phương pháp cổ điển để giải hệ phương trình đại số tuyến tính (SLAE). Đây là phương pháp loại trừ tuần tự các biến khi sử dụng biến đổi cơ bản hệ phương trình được rút gọn thành một hệ tương đương có dạng bậc (hoặc tam giác), từ đó tất cả các biến khác được tìm theo thứ tự, bắt đầu với các biến cuối cùng (theo số).

Nói một cách chính xác, phương pháp mô tả ở trên được gọi đúng là phương pháp khử Gauss-Jordan, vì nó là một biến thể của phương pháp Gauss được nhà khảo sát Wilhelm Jordan mô tả năm 1887). Cũng có một điều thú vị là cùng thời với Jordan (và theo một số nguồn kể cả trước anh ta), thuật toán này được phát minh bởi Clasen (B.-I. Clasen).

Dưới phương trình phi tuyếnđược hiểu là các phương trình đại số và siêu nghiệm có dạng, trong đó x - số thực, một - chức năng phi tuyến. Để giải các phương trình này, phương pháp hợp âm được sử dụng - lặp lại phương pháp số tìm gần đúng của rễ. Như đã biết, nhiều phương trình, hệ phương trình không có nghiệm phân tích. Trước hết, điều này áp dụng cho hầu hết các phương trình siêu nghiệm. Nó cũng được chứng minh rằng không thể xây dựng một công thức mà có thể giải một phương trình đại số tùy ý có bậc cao hơn bậc bốn. Ngoài ra, trong một số trường hợp, phương trình chứa các hệ số chỉ được biết gần đúng, và do đó, vấn đề định nghĩa chính xác nghiệm của phương trình là vô nghĩa. Để giải quyết chúng, phương pháp lặp với một mức độ chính xác nhất định được sử dụng. Giải một phương trình bằng phương pháp lặp có nghĩa là xác định xem nó có nghiệm nguyên hay không, có bao nhiêu nghiệm nguyên và tìm giá trị của các nghiệm nguyên với độ chính xác cần thiết.

Bài toán tìm nghiệm nguyên của phương trình f (x) = 0 bằng phương pháp lặp gồm hai giai đoạn:

tách các gốc - tìm giá trị gần đúng của gốc hoặc đoạn chứa nó;

· Tinh chỉnh các gốc gần đúng - đưa chúng đến một mức độ chính xác nhất định.

tích phân xác định hàm f (x) nhận trong khoảng từ một trước b, được gọi là giới hạn mà tổng tích phân có xu hướng khi tất cả các khoảng ∆x i có xu hướng bằng không. Theo quy tắc hình thang, cần thay đồ thị của hàm số F (x) bằng một đường thẳng đi qua hai điểm (x 0, y 0) và (x 0 + h, y 1) thì tính giá trị của phần tử của tổng tích phân là diện tích của hình thang: .

GIẢI PHÁP CHẬM CHẬM BẰNG PHƯƠNG PHÁP ĐIỀU KHIỂN ĐƠN GIẢN

1.1 Mô tả phương pháp lặp hằng số

Hệ phương trình đại số (SLAE) có dạng:

hoặc, khi được viết dưới dạng ma trận:

Trong thực tế, hai loại phương pháp được sử dụng giải pháp số SLAE - trực tiếp và gián tiếp. Khi sử dụng các phương pháp trực tiếp, SLAE được giảm xuống thành một trong những hình dạng đặc biệt (đường chéo, hình tam giác) cho phép bạn thu được chính xác lời giải mong muốn (nếu nó tồn tại). Phương pháp trực tiếp phổ biến nhất để giải SLAE là phương pháp Gauss. Các phương pháp lặp lại được sử dụng để tìm giải pháp gần đúng của SLAE với độ chính xác nhất định. Cần lưu ý rằng quá trình lặp không phải lúc nào cũng hội tụ về nghiệm của hệ mà chỉ khi chuỗi các phép tính gần đúng thu được trong các phép tính có xu hướng về một nghiệm chính xác. Khi giải SLAE bằng phương pháp lặp đơn giản, nó được chuyển sang dạng khi chỉ có một trong các biến bắt buộc nằm ở phía bên trái:

Đã đưa ra một số ước tính ban đầu xi, i = 1,2,…, n, thay thế chúng thành bên phải biểu thức và tính toán các giá trị mới x. Quá trình này được lặp lại cho đến khi lượng dư tối đa được xác định bởi biểu thức:

không trở nên nhỏ hơn độ chính xác đã cho ε. Nếu sự khác biệt lớn nhất ở k-lần lặp thứ sẽ lớn hơn sự khác biệt tối đa tại k-1-lặp lại lần thứ, sau đó quá trình kết thúc bất thường, bởi vì quá trình lặp đi lặp lại phân kỳ. Để giảm thiểu số lần lặp, các giá trị x mới có thể được tính bằng cách sử dụng các giá trị còn lại từ lần lặp trước.

Bài giảng Phương pháp lặp để giải hệ phương trình tuyến tính đại số.

Điều kiện hội tụ của quá trình lặp lại. Phương pháp Jacobi. Phương pháp Seidel

Phương pháp lặp lại đơn giản

Hệ phương trình đại số tuyến tính được coi là

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

Sau đó, giá trị gần đúng ban đầu cho nghiệm của hệ phương trình được chọn và một dãy các giá trị gần đúng với nghiệm nguyên được tìm thấy.

Để quá trình lặp đi lặp lại hội tụ, điều kiện là đủ
(định mức ma trận). Tiêu chí kết thúc cho các lần lặp phụ thuộc vào phương pháp lặp lại được áp dụng.

Phương pháp Jacobi .

Cách đơn giản nhất để đưa hệ thống về dạng thuận tiện cho việc lặp lại như sau:

Từ phương trình đầu tiên của hệ, chúng ta biểu diễn ẩn số x 1, từ phương trình thứ hai của hệ thống, chúng tôi biểu diễn x 2, v.v.

Kết quả là ta thu được một hệ phương trình với ma trận B, trong đó các phần tử không nằm trên đường chéo chính, các phần tử còn lại được tính theo công thức:

Các thành phần của vectơ d được tính theo công thức:

Công thức tính của phương pháp lặp đơn giản là:

hoặc trong ký hiệu tọa độ trông như thế này:

Tiêu chí chấm dứt các lần lặp trong phương pháp Jacobi có dạng:

Nếu một
, sau đó có thể áp dụng một tiêu chí đơn giản hơn để chấm dứt các lần lặp lại

ví dụ 1 Giải hệ phương trình tuyến tính theo phương pháp Jacobi.

Cho hệ phương trình đã cho:

Nó được yêu cầu để tìm ra một giải pháp cho hệ thống với độ chính xác

Chúng tôi đưa hệ thống về một biểu mẫu thuận tiện cho việc lặp lại:

Chúng tôi chọn một giá trị gần đúng ban đầu, ví dụ:

là vectơ của vế phải.

Sau đó, lần lặp đầu tiên trông giống như sau:

Các giải pháp gần đúng sau đây thu được tương tự.

Tìm chuẩn của ma trận B.

Chúng tôi sẽ sử dụng định mức

Vì tổng môđun của các phần tử trong mỗi hàng là 0,2, nên
, vì vậy tiêu chí để chấm dứt lặp lại trong vấn đề này là

Hãy để chúng tôi tính toán các tiêu chuẩn của sự khác biệt của các vectơ:

Tại vì
độ chính xác được chỉ định đạt được ở lần lặp thứ tư.

Câu trả lời: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Phương pháp Seidel .

Phương pháp này có thể được coi là một sửa đổi của phương pháp Jacobi. Ý tưởng chính là khi tính toán tiếp theo (n + 1)-thể hiện gần đúng với điều chưa biết x tôi tại tôi> 1 sử dụng đã được tìm thấy (n + 1) - tiếp cận điều chưa biết x 1 ,x 2 , ...,x tôi - 1, không phải N xấp xỉ thứ, như trong phương pháp Jacobi.

Công thức tính toán của phương pháp trong ký hiệu tọa độ trông giống như sau:

Các điều kiện hội tụ và tiêu chí kết thúc cho các lần lặp có thể được thực hiện giống như trong phương pháp Jacobi.

Ví dụ 2 Giải hệ phương trình tuyến tính bằng phương pháp Seidel.

Xét song song nghiệm của 3 hệ phương trình:

Chúng tôi đưa các hệ thống về dạng thuận tiện cho việc lặp lại:

Lưu ý rằng điều kiện hội tụ
chỉ thực hiện cho hệ thống đầu tiên. Chúng tôi tính toán 3 giá trị gần đúng đầu tiên cho lời giải trong mỗi trường hợp.

Hệ thống thứ nhất:

Giải pháp chính xác sẽ là các giá trị: x 1 = 1.4, x 2 = 0.2 . Quá trình lặp lại hội tụ.

Hệ thống thứ 2:

Có thể thấy rằng quá trình lặp đi lặp lại phân kỳ.

Giải pháp chính xác x 1 = 1, x 2 = 0.2 .

Hệ thống thứ 3:

Có thể thấy rằng quy trình lặp đi lặp lại.

Giải pháp chính xác x 1 = 1, x 2 = 2 .

Cho ma trận của hệ phương trình A là ma trận đối xứng và xác định dương. Sau đó, đối với bất kỳ lựa chọn nào về ước lượng ban đầu, phương pháp Seidel sẽ hội tụ. Các điều kiện bổ sung về độ nhỏ của tiêu chuẩn của một số ma trận không được áp đặt ở đây.

Phương pháp lặp lại đơn giản.

Nếu A là ma trận xác định đối xứng và dương thì hệ phương trình thường được rút gọn về dạng tương đương:

x=x-τ (A x- b), τ là tham số lặp.

Công thức tính toán của phương pháp lặp đơn giản trong trường hợp này là:

x (n + 1) =x N- τ (A x (N) - b).

và tham số τ> 0 được chọn để, nếu có thể, giá trị nhỏ nhất

Gọi λ min và λ max là các giá trị riêng nhỏ nhất và lớn nhất của ma trận A. Lựa chọn tối ưu là tham số

Trong trường hợp này
chấp nhận giá trị tối thiểu tương đương với:

Ví dụ 3 Giải hệ phương trình tuyến tính bằng phép lặp đơn giản. (trong MathCAD)

Cho hệ phương trình Ax = b

Để xây dựng một quy trình lặp đi lặp lại tìm của riêng chúng tôi số của ma trận A:

- sử dụng một chức năng cài sẵn để tìm giá trị riêng.

Tính tham số lặp và kiểm tra điều kiện hội tụ

Điều kiện hội tụ được thỏa mãn.

Hãy lấy giá trị gần đúng ban đầu - vectơ x0, đặt độ chính xác là 0,001 và tìm các giá trị gần đúng ban đầu bằng chương trình dưới đây:

Giải pháp chính xác

Bình luận. Nếu chương trình trả về ma trận rez, thì bạn có thể xem tất cả các lần lặp được tìm thấy.