Курсавая. Курсавая 1. Методы решения алгебраических и трансцендентных уравнений

• Название: Методы решения алгебраических и трансцендентных уравнений
• Анкор: Курсавая
• Дата: 22.06.2022
• Размер: 0.64 Mb.
• Имя файла: Курсавая 1.docx
• Тип: Курсовая; #610528
• страница: 3 из 9

1.4 Метод Краута − Дулитла

Идея сводится к представлению матрицы Aпроизведением нижней и верхней треугольных матриц A= L U, где

^l11

0 ... 0 _

^u11

^u12

...

^u1n^

_ 
^l21

L

^l22

...

₀   ₀

^ , U <sup>

u</sup>22

...

^u2n^



.

 ... ...

... ... 

 ... ...

... ... 

^l l

... l ^{ } 0 0

... u ^

 n1 n2

nn 

nn

Выполняя их умножение, приходим к системе n² уравнений

l

^aij

 _l_ik

k1

^ukj; i, j= 1, 2, …, n

c n² + n неизвестными, которую можно решить однозначно лишь задав n неизвестных равными каким-то константам (например, равными 1). Такое разложение в литературе называют схемой Ха- лецкого (Холецкого?), а предложенные в 1941 г. на ее основе ме- тоды решения системы А Х = В методом Краута (элементы глав- ной диагонали матрицы U равны единице) или методом Дулитла (главная диагональ матрицы Lединичная) [8].

Возьмем для примера систему АХ= D и разложение

A= B C, где

^b11


_ 
^b21

B

0

^b22

...

...

0 _{ }1




0
₀

^ , C <sup>

c</sup>12

1

...

...

^c1n^


 _.
^c2n^

 ... ...

... ... 

... ...

... ... 

^b b ... b ^{ }0 0 ... 1 ^

 n1 n2 nn ^{ }

Перемножая эти матрицы, мы получаем систему n² уравнений c n²

неизвестными, решение которой можно отыскать в виде

b_i1 = a_i1 (i= 1, 2, …, n); c_1j= a_1j/ b₁₁ (j= 2, 3, …, n);

c  ¹ (a

i1

• 
  b
  

c ) (i 2, 3, …,

j 1);

b
ij ij

ii



k1

ik kj
i1

^bij

 a_ij

• 
  _b_ik
  

k1

c (i j)

kj

(находим первый столбец матрицы Bи первую строку C, затем второй столбец Bи вторую строку Cи т. д.).

Так при n= 3 последовательно находим значения

b₁₁  a₁₁,

b₂₁  a₂₁,

b₃₁  a₃₁ ,

c₁₁  1,

^c12

 a₁₂/b₁₁,

^c13

 a₁₃/b₁₁,

^b22

^{ a}22 ^{ b}21 ^c12

, b₃₂

 a₃₂  b₃₁ c₁₂ ,

^c22

 1,

^c23

 ¹ (c₂₃  b₂₁ c₁₃ ),


b
22

^b33

^{ a}33 ^{ b}31 ^c13 ^{ b}32 ^c23 <sup>,

c</sup>33

 1.

Для матрицы из рассмотренного выше примера имеем

	3	–1	0	b11 = 3, b21 = −2, b31 = 2,
A=	−2	1	1	c11 = 1, c12 = −1/3, c13 = 0,
	2	−1	4	b22 =1−(−2)(−1/3)=1/3, b32 = −1− (2)(−1/3) = −1/3,

Отсюда

c₂₂ = 1, c₂₃ = [1−(−2)  (0)] / (1/3) = 3,

b₃₃ = 4 − (2 )  (0) − (–1/3)  (3) = 5, c₃₃ = 1.

3	−1	0		3	0	0		1	−1/3	0
−2	1	1	=	−2	1/3	0		0	1	3
2	−1	4		2	−1/3	5		0	0	1

Получив такое разложение, имеем В  С  X = D и, выполнив замену С  X = Y, приходим к системе двух уравнений с треуголь- ными матрицами коэффициентов B  Y = D и С  X = Y, решение которых достаточно просто

y ^d1 , y

_1 ^ _d

i1 _


,
 by i 2, 3,…, n;

1 _b i

_b _i

^ ik k^

11 i_

k1 

n

x_n

y_n,

10. 
    
    

y_i

_c_ik x_k,

ki1

i n 1, n 2,…,1.

Так для нашего примера возникают системы

3	0	0		y1		5		1	−1/3	0		x1		y1
−2	1/3	0		y2	=	0	,	0	1	3		x2	=	y2
2	−1/3	5		y3		15		0	0	1		x3		y3

откуда получаем

y₁ = 5/3, y₂ = [0 − (−2)  (5/3)] / (1/3) = 10,

y₃ = [15 − (2)  (5/3) − (−1/3)  (10)] / 5 = 3,

x₃ = 3, x₂ = 10 − (3)  (3) = 1, x₁ = 5/3 − (−1/3)  (1) − (0)  (3) = 2.

Количество арифметических операций при реализации метода Краута имеет тот же порядок, что и метода Гаусса.