Итерационные методы решения систем линейных уравнений с неединственными коэффициентами
Реферат - Математика и статистика
Другие рефераты по предмету Математика и статистика
µкторов , определив её рекуррентно:
(k = 0,1,2,…..) (2.2)
при произвольном выборе нулевого приближения.
Таким образом, метод простой итерации сводится к замене точного решения системы (1.1) k ой итерацией с достаточно большим номером k.
Графически метод Якоби можно представить следующим образом:
Рис. 1. Схема выполнения метода Якоби
Оценим погрешность метода простой итерации. Очевидно, что
,(2.3)
где Е единичная матрица.
Введем в рассмотрение норму вектора в пространстве и операторную норму квадратной матрицы порядка . Назовем нормой вектора число , равное длине вектора. Назовем операторной нормой произвольной матрицы число , равное либо точной верхней грани отношения на множестве всех ненулевых векторов , либо (что одно и то же) точной верхней грани норм на множестве всех векторов , имеющих единичную норму. Т.е по определению
.(2.4)
Из (2.4) вытекает неравенство, справедливое для любой матрицы и любого вектора :
.(2.5)
Из матричного уравнения погрешности (2.3) и неравенства (2.5) получаем, что для любого номера :
.(2.6)
Теорема 2.1. Для того, чтобы итерационная последовательность (2.2) при любом выборе начального приближения и при данном значении параметра сходилась к точному решению системы (1.2), достаточно, чтобы было выполнено условие
.(2.7)
При этом итерационная последовательность сходится со скоростью геометрической последовательности со знаменателем .
В случае если матрица является симметричной, условие является необходимым условием сходимости итерационной последовательности при любом выборе нулевого приближения.
Для практических же целей недостаточно установить факт сходимости последовательности итераций. Центральным вопросом является оценка скорости сходимости. Очень важно знать, как наилучшим способом распорядиться стационарным параметром для того, чтобы получить наиболее быструю сходимость.
Пусть задана точность - точность, с которой необходимо получить решение системы. Требуется найти итерацию с таким номером , для которого
.(2.8)
Из (2.6) и Теоремы 2.1 следует, что , и (2.8) выполняется при условии , т.е при . Отсюда видно, что для уменьшения числа итераций , достаточных для достижения заданной - точности, следует выбрать параметр так, чтобы получить минимум функции .
Считая матрицу симметричной и положительно определенной, мы приходим к следующей задачей оптимизации: найти минимум функции
.
Теорема 2.2 (Теорема А.А. Самарского). Пусть матрица является симметричной и положительно определенной, а матрица положительно определенной. Тогда для того, чтобы итерационная последовательность
(2.9)
при любом выборе нулевого приближения сходилась к точному решению системы , достаточно, чтобы были выполнены условия
(2.10)
При дополнительно предположении о том, что матица является симметричной, условие (2.10) не только достаточно, но и необходимо для сходимости указанной итерационной последовательности с любым нулевым приближением .
Выражение (2.9), где представляет себя некоторую легко обратимую квадратную матрицу - го порядка, а - стационарный параметр, получается из выражения (2.2) . Такой метод является более общим методом по сравнению с методом простой итерации и называется неявным методом простой итерации.
Перейдем теперь к оценке сходимости общего неявного метода простой итерации. Для этого выясним вопрос о выборе стационарного параметра , обеспечивающего наиболее быструю сходимость последовательности.
Предположим, что является симметричной и положительно определенной. С помощью таких матриц естественно ввести так называемое энергетическое скалярное произведение двух произвольных векторов и , положив его равным Такое скалярное произведение будем обозначать . С помощью матрицы это скалярное произведение можно записать в виде С помощью последнего равенства легко проверяется справедливость для введенного нами скалярного произведения четырех аксиом скалярного произведения.
Далее естественно ввести энергетическую норму вектора , положив ее равной . Эту энергетическую норму обозначим как .
Две различных нормы одной и той же системы векторов и называются эквивалентными, если существуют такие положительные постоянные и , что справедливы неравенства
.(2.11)
Энергетическая и обычная нормы вектора являются эквивалентными, а это позволяет утверждать, что последовательность сходится к нулю тогда и только тогда, когда сходится к нулю последовательность . Для дальнейших же рассуждений энергетическая форма более удобна.
Теорема 2.3 Пусть матрица и симметричны и положительно определены, - погрешность общего неявного метода простой итерации. Тогда для того, чтобы при было справедливо неравенство , необходимо и достаточно, чтобы было выполнено следующее условие
(2.12)
Применим Теорему 2.3 для нахождения значения стационарного параметра , при котором скорость сходимости будет максимальной. Как уже было сказано выше, для этого необходимо найти минимум функции
Так как обе матрицы и являются симметричными и положительно определенными, то существуют такие постоянные и , что справедливы неравенства . Будем считать, что посто