Практикум j практическое примщенше численных методов

i-¹ _x / 3-1 \
Uij a^j ^ ^ lik'U'kj ? Iji I Q>ji ^ ^ Ijk'U'ki J ?
fc= 1 ^Uii \ k=l J
г = 2,3,..., n, j = i + 1, i + 2,..., n.
Эти формулы определяют компактную схему метода Гаусса для разложения матрицы на множители.
После того как разложение (4.4) проведено решение системы уравнений сво. дится к последовательному решению двух систем уравнений с треугольными матрицами:
Ly = /, (4.5)
Ux = y. (4.6)
Разложение (4.4) и решение системы (4.5) связывается с прямым ходом в ме­тоде исключения неизвестных, а решение системы (4.6) — с обратным ходом.
В методе Гаусса с выбором главного элемента на очередном шаге исключается неизвестное, коэффициент по модулю при котором является наибольшим. В этом случае метод Гаусса применим для любых невырожденных матриц Л, т.е. матриц, для которых det(A) ф 0).
Матрицей перестановок Р называется квадратная матрица, у которой в каж­дой строке и в каждом столбце только один элемент отличен от нуля и равен единице. При det(A) ф 0 существует матрица перестановок Р такая, что справедливо разложение
. РА = LU.
Тем самым метод Гаусса с выбором главного элемента соответствует приме­нению обычного метода Гаусса, который применяется^ к системе, полученной из исходной системы перестановкой некоторых уравнений.
Метод квадратного корня
При решении системы уравнений (4.1) с симметричной вещественной невы­рожденной матрицей А используется разложение
А = S*DS,
где S — верхняя треугольная матрица с положительными элементами па главной диагонали, S* — транспонированная к ней (s*j = Sji), a D — диаго­нальная матрица с элементами d*, г = 1,2,... , п, равными =Ы. Вычисления на основе этого разложения определяют метод квадратного корня (метод Хо- лецкого).
Для элементов матриц S и D используются расчетные формулы:
d\ = sign йц, s_u = |a_u|^1/2, з_ц=а_ц/«_ш j = 2,3,...,n,
di = sign |a_tt - '^2 l«fci|²4^ ,
1/2
8ц — (1ц ^ ^ dfc i
к= 1
^Sij ⁼ ~ ^Ski³kjdk^ j
г = 2,3,..., 71, j = i + 1, i + 2,..., n.
В методе квадратного корня вычислительные затраты примерно в два раза меньше, чем в стандартном методе Гаусса (эффект учета симметрии матрицы задачи).

2. 
   Упражнения
   

Ниже приведены примеры построения программ на языке Python для чис­ленного решения систем линейных уравнений прямыми методами линейной алгебры. Мы ограничиваемся основными возможностями базового математи­ческого пакета NumPy (поддержка работы с многомерными массивами).
Упражнение 4.1 Напишите программу, реализующую решение системы линейных алгебраических уравнений па основе LU-разлоэ1сения. С ее помо­щью найдите решение системы
Ах — f
с матрицей
j

1,	i = j,
-1,	i < 3,
0,	i > j Ф rc,
1,	3=n,
	Л = 1,

&ij —

и правой частью

i — 1,2,..., п,

i = 1,2, ...,п
= 1,2,..., гс
при п = 10.
В модуле lu функция decLUO проводит LU-разложение входной матрицы А и записывает результат в матрицу LU. Реализация (4.5), (4.6) для решения системы уравнений проводится функцией solveLUO.
Модуль lu
import numpy as np <*ef decLU(A):
и и и
Returns the decompositon LU for matrix A.
и и и
п = 1еп(А)
LU = пр.сору(А)
for j in range(0,n-l):
for i in range(j+l,n):
if LU[i,j] != 0.:
u = LU[i, j] / LU[j , j]
LU[i,j+l:n] = LU[i,j+l:n] - u*LU[j, j+1 :n]
LU[i, j] = u
return LU
def solveLU(A, f):
к и и
Solve the linear system Ax = b.
и и и
n = len(A)

• 
  LU decomposition LU = decLU(A)
  

x = np.copy(f)

• 
  forward substitution process for i in range(l,n):
  

x[i] = x[i] - np.dot(LU[i,0:i], x[0:i])

• 
  back substitution process for i in range(n-1,-1,-1):
  

x[i] = (x[i] - np.dot(LU[i,i+l:n], x[i+l:n])) / LU[i,i] return x
Решение нашей конкретной системы линейных алгебраических уравнений да­ется следующей программой.
1И11Ш1118!!3^
import numpy as np
from lu import decLU, solveLU
n = 8
A = -np.ones((n, n), ’float’) for i in range(0,n):
A[i,i] = 1.
A[i,n-1] = 1. if i < n-1:
A[i,i+1:n-l] =0. print ’A:\n’, A LU = decLU(A) print ’LU:\n’, LU f = np.ones((n), ’float’) print ’b:\n’, f x = solveLU(A, f) print ’x:\n’, x

А

[[ 1	0		0		0			0		0	0		ill	1
1-1	1.		0/		0.			0.		0	0.		ill	1
1-1	-1		1		0			0		0	• 0		■1	1
[-1	-1.		-1.		1			0		0	0		■1	1 M
1-1	-1		; —1 .		-:1			1		0	0	IIS	■I	1 .
(-1	-1		-1;		-1.					IV;	life		m	imm		illll
М-1	-1,				-1;			-if			), -ill	illll	i-]	ть
М-1 Т-ТТ ■■■ •	Sill!		-L,		-1			-i		■Ш ■				{.p,.
|||\			|о			0i		Illll		0.		0.		0.	’ 0	MM,