Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
0-5
Лекция 9
4.4.4. QR-алгоритм решения СЛАУ
Рассмотрим другой метод приведения матриц к треугольному виду – метод вращения. Этот метод позволяет получить представление исходной матрицы в виде произведения ортогональной матрицы на верхнюю треугольную матрицу :
. (4.41)
На первом шаге прямого хода, состоящем из «малых» шагов, также как и в методе Гаусса, исключаем неизвестное из всех уравнений, начиная со второго. Для исключения из второго уравнения вычисляют числа
, , (4.42)
для которых выполняется условия:
, . (4.43)
Затем первое уравнение системы заменяют линейной комбинацией первого и второго уравнений с коэффициентами и , а второе уравнение — линейной комбинацией первого и второго уравнений с коэффициентами и . В результате получим систему вида
(4.44)
в которой
, , , (4.45)
, . (4.46)
Так как , то .
Преобразование исходной системы (4.1) к виду (4.4) эквивалентно умножению слева матрицы на матрицу и правую часть , где матрица имеет вид
.
Для исключения неизвестного из третьего уравнения вычислим числа
, , (4.47)
удовлетворяющие условиям , . Далее, первое уравнение системы (4.44) заменим линейной комбинацией первого и третьего уравнений системы с коэффициентами и , а третье уравнение заменяем комбинацией с коэффициентами и . Это преобразование системы эквивалентно умножению слева на матрицу
в результате чего, коэффициент при в преобразованном третьем уравнении обращается в нуль.
Таким же образом исключаем из уравнений с номерами . После завершения 1-го шага система приводится к виду
(4.48)
В матричной форме (4.48) имеет вид:
,
где , .
Здесь через обозначена матрица элементарного преобразования, отличающаяся от единичной матрицы только четырьмя элементами, а именно, элементы с индексами и равны , элемент с индексами равен , а элемент с индексами равен . Элементы и удовлетворяют условию
. (4.49)
Действие матрицы на вектор эквивалентно его повороту вокруг оси, перпендикулярной плоскости на угол такой, что , . По этой причине метод назвали методом вращений. Матрица ортогональна, т.е. .
На втором шаге метода вращений, состоящем из «малых» шагов, из уравнений системы (4.35) с номерами исключают неизвестное . Для этого каждое -е уравнение комбинируют со вторым уравнением. В результате получим систему
В матричной форме эта запись имеет вид
,
где , .
После завершения -го шага система примет вид
или в матричной форме
,
где , .
Обозначим за матрицу . Тогда матрица и связаны соотношением
,
где – матрица результирующего вращения. Отметим, что матрица ортогональна, как произведение ортогональных матриц. Обозначая , получаем -разложение матрицы .
Обратный ход метода вращений совпадает с обратным ходом метода Гаусса.
Метод вращений обладает хорошей вычислительной устойчивостью. Погрешность решения может быть оценена по формуле
,
где – машинное эпсилон (машинный нуль). Однако этот метод значительно более трудоемок по сравнению с методом Гаусса. Для квадратной матрицы требуется примерно арифметических операций.
4.5 Метод итерации решения СЛАУ
При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае для решения СЛАУ иногда удобнее пользоваться приближенными методами. Рассмотрим один из приближенных методов – метод итерации.
Итак имеем СЛАУ
(4.50)
Предполагая, что разрешим первое уравнение системы (14) относительно , второе – относительно ,…,-ое уравнение – относительно . В результате получим
(4.51)
где ; при . Система (4.51) в матричной форме имеет вид
(4.52)
Систему (4.52) будем решать методом последовательных приближений. Пусть , тогда
(4.53)
Если последовательность имеет предел , то этот предел является решением системы (4.52). В самом деле, переходя к пределу в равенстве (4.53) будем иметь , то есть предельный вектор является решением системы (14).
Теорема 2: Если , то система уравнений (4.52) имеет единственное решение и итерационный процесс (4.53) сходится к решению независимо от начального приближения.
Доказательство: Имеем
Тогда
Отсюда
Поэтому, если , то последовательность является сходящейся, то есть
Тогда, переходя к пределу в итерационном процессе
получим ч.т.д.
Следствие: Для системы
метод итераций сходится, если выполнены неравенства
(4.54)
Действительно, для системы (4.52)
сходимость процесса выполняется, если . Так как
, то из определения нормы матрицы получим (4.54).
4.6 Метод Зейделя
Метод Зейделя представляет собой модификацию метода итераций.
Пусть дана приведённая система:
и известно начальное приближение . Основная идея заключается в том, что при вычислении (k+1) - го приближения неизвестной учитываются уже вычисленные ранее (k+1) - приближение неизвестных .
Итерационная схема имеет вид:
Положим , где
;
Тогда процесс Зейделя в матричном виде можно записать как:
Достаточное условие сходимости процесса Зейделя такие же, как и для метода итераций.
4.6.1 Достаточные условия сходимости процесса Зейделя.
Теорема 4. Если для линейной системы
(55)
выполняется условие , то процесс Зейделя для системы (55) сходится к единственному её решению при любом выборе начального вектора .
Доказательство
Рассмотрим сходимость процесса для нормы
(56)
Для k - го приближения имеем
(57)
Вычтем (57) из точного решения
(58)
Для -ой компоненты вектора из (58) имеем
Отсюда:
(59)
Так как (59) справедливо для любого , то оно будет справедливо и для , при котором:
Следовательно, из (59) имеем:
(60)
где
Таким образом из (60) получим:
(61)
Оценим . Покажем, что
Так как , то
Следовательно:
Из (61) имеем:
При ч.т.д.
4.7 Оценка погрешности процесса Зейделя
Запишем разность
(62)
Прибавим и отнимем в правой части (62) слагаемое
(63)
Переходя в (63) к нормам, получим
.
Отсюда следует
(64)
Из (64) следует, что в качестве критерия окончания итерационного процесса следует брать
(65)
Если мала (), то вместо (65) можно использовать
(65а)
Самостоятельно изучить следующие вопросы.
Решение СЛАУ методом ортогонализации и методом Халецкого.
Решение переопределенной СЛАУ методом наименьших квадратов.
Вычисление определителей методом Гаусса и методом Халецкого.
Вычисление обратной матрицы.