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

3 = 1
На основе экспериментов со случайными матрицами при различных п убе­дитесь в выполнении неравенств
^1И11а < |И||е < s/n\\A\\_a, а = 1,00
для евклидовой (сферической) нормы (нормы Фробениуса) ЦАЦ#.
Задача 4.2 Напишите программу, реализующую LU-разлоэюепие с выбором главного элемента по строке (схема частичного выбора) с выводом мат­рицы LU и вектора перенумерации переменных (перестановки столбцов),
который определяет матрицу перестановок Р. С ее помощью найдите LJJ. разлоэюение матрицы Паскаля, для которой
₌
i = 1,2.

(i + j-2)1
⁴ⁱ (i-mj-iy.
Проверьте выполнение det(A) = 1 и зависимость определителя от п. По- вторите эксперименты с LU-разлоэюеиием без выбора главного элемента (модуль 1и).
Задача 4.3 Разработайте алгоритм и реализуйте его программно для ва­рианта декомпозиции Холецкого симметричной невыроэюденной матрицы в виде А = LDL*, где L — ниэюняя треугольная матрица с единичной диа­гональю и D — диагональная матрица, без вычисления квадратного корня. С помощью этой программы найдите декомпозицию Холецкого KMS (К ас- Murdock-Szego) матрицы, для которой
di)=e^b~^}\ г = 1,2,..., п, j = 1,2,
При различных п и q сравните рассчитанную матрицу D с точным реше­нием, для которого
₌ ^{< = 1}> ^и \ l-e², i = 2,3,...,п.
Задача 4.4 Рассмотрите алгоритм построения обратной матрицы на основе решения матричного уравнения
АХ = Е,
где Е —■ единичная, а X — искомая квадратная матрица. Напишите про­грамму вычисления обратной матрицы на основе LU-разлоэ1сение с выбором главного элемента по строке (схема частичного выбора) (задача 4-2). Най­дите обратную к матрице Лемера (Lehmer), для которой
г
шт(г, j) тах(г, j) ’
= 1,2, j = 1,2,
При вычислениях с различными значениями п убедитесь в том, что А ¹ является трехдиагональной матрицей.
Задача 4.5 Напишите программу для вычисления числа обусловленности квадратной матрицы с использованием норм || • ||„, а = 1,Е,ос (см. зада­чу 4-1) и вычисления обратной матрицы на основе LU-разлоэюение матрицы (упразднение 4-1). Найдите при различных п число обусловленности мат­рицы А, в которой
Убедитесь, что обратная матрица является трехдиагональной, внедиаго- иальиые элементы которой а”/_±1 = —I, а диагональные —
-1 Г 2, 2 = 1,2, ...,п — 1,
’■* ~ \ 1, г — п.
Задача 4.6 Рассмотрите алгоритм решения системы уравнений с трех­диагональной циклической матрицей, элементы которой ац = 0 при 1 < \i — j\ < п — 1 (а\_п Ф О, a_ni фО), на основе LU-разлоэюения. Покаэюите, что в этом случае
lij ф О, 2 = 1,2, ..., 71 1, j — 2, 2 1, % — 71, j ⁼ 1,2, 71,
Uij ф О, j = 1,2 ,...,71 - 1 2 =j,j - 1, j =71, i = 1,2,n,
и напишите программу решения задачи Ах = f. Найдите решение уравнения с циклической трехдиагональной матрицей, для которой
ац 2 ~Ь h , 1, а\_п — а_пi = 1
при правой части
fi = ^1 + ^ sin²(7r/i)^ sin(27r(2 - l)/l), 2 = 1,2, ..., 71
где h = 7i~¹. Покажите, что
yi = sin(27r(2 - 1 )h), 2 = 1,2,..., n
есть 7почное решение рассматриваемой задачи.

Итерационные методы линейной алгебры
Для приближенного решения больших систем линейных алгебраических урав­нений используются итерационные методы. Такие системы возникают при приближенном решении многомерных краевых задач математической физи­ки. Рассмотрение начинается с классических итерационных методов Якоби и Зейделя. Приведены базовые понятия теории итерационных методов реше­ния систем линейных уравнений, рассматриваемых в евклидовых простран­ствах. Обсуждаются проблемы выбора итерационных параметров, матрицы перехода (переобуславливателя).

Основные обозначения
Х= {Xi} = {хих2,...,хп}	— n-мерный вектор
А = {<2ц }	— матрица с элементами
Е	— единичная матрица
D = diag {dud2,...,dn}	— диагональная матрица
ы	— норма вектора х
1И11	— норма матрицы А
х^к	— приближенное решение на к-й итерации
z^k = X^к - X	— погрешность приближенного решения
?г II ?г 1	— невязка на к-й итерации
Т,тк	— итерационные параметры

1. 
   Итерационное решение систем линейных уравнений
   

Рассматриваются проблемы итерационного решения системы линейных уран- нений
Ах = f (5.1)
для нахождения вектора х. В теории итерационных методов матрица А обыч­но рассматривается как линейный оператор, действующий на евклидовом

пространстве Н = /₂, в котором скалярное произведение есть (х,у) = У^ж^,
г=1
а норма \\х\\ = (ж,ж)^1/2.
Итерационный метод основан на том, что начиная с некоторого начального приближения х° 6 Н последовательно определяются приближенные реше­ния уравнения (5.1) ж¹, ж²,..., х^к,..., где к — номер итерации. Значения x^k+l определяются по ранее найденным х^к, ж*^-1,..,. Если при вычислении х^к+1 используются только значения на предыдущей итерации х^к, то итерационный метод называется одношаговым (двухслойным). Соответственно, при исполь­зовании х^к и х^к~^г итерационный метод называется двухшаговым (трехслой­ным).
Двухслойный итерационный метод записывается в следующей канонической форме
_хк+1 _ „к
В— 1-Ax^k = f, к = 0,1,— (5.2)
^тк+1
Для характеристики точности приближенного решения естественно ввести погрешность z^k = х^к — х. Будем рассматривать сходимость итерационного метода в энергетическом пространстве Hr, порожденном симметричной и положительно определенной матрицей R. В H_R скалярное произведение и норма есть
(v,w)r = (Ry,w), |М|я = ((у,2/)я)^1/2-
Итерационный метод сходится в Hr, если \\z^k\\R —► 0 при к —> оо. В качестве меры сходимости итераций принимают относительную погрешность е, так что на К-й итерации
||я* -х||я < £||ж° -а;||я. (5.3)
В силу того, что само точное решение х неизвестно, оценка точности прибли­женного решения проводится по невязке
r^k = Ax^k-f = Ах^к - Ах,
которая может быть вычислена непосредственно. Например, итерационный процесс проводится до выполнения оценки
1|г*||<ф°||. (5.4)
Использование критерия сходимости (5.4) соответствует выбору R = А*А в (5.3). Минимальное число итераций, которое гарантирует точность е (выпол­нение (5.3) или (5.4)), обозначим К(е).
При построении итерационного метода мы должны стремиться к минимиза­ции вычислительной работы по нахождению приближенного решения задачи (5.1) с заданной точностью. Пусть Q_k — число арифметических действий для
нахождения приближения х^к и пусть делается К > К(е) итераций. Тогда о(у. щие затраты оцениваются величиной