Практическое задание. Глава 7. Численные методы алгебры

Глава 7. Численные методы алгебры.

ИТЕРАЦИОННЫЕ МЕТОДЫ РешениЯ систем лИнейных уравнений

При решении систем уравнений высоких порядков зачастую матрицы их являются разреженными – основная часть их коэффициентов являются нулевыми. Такие матрицы невыгодно хранить в виде обычных массивов, поскольку их нулевые элементы будут занимать слишком много места в памяти вычислительного устройства. Для них применяется выборочное хранение ненулевых элементов.

При решении систем линейных уравнений с разреженными матрицами наиболее эффективными являются итерационные методы.

Идея итерационных методов. Основные понятия

Итерационные методы позволяют определить решение системы линейных уравнений с заранее заданной точностью в виде последовательности приближенных решений `х <sup>( i )</sup>=(х <sub>1</sub> <sup>i</sup>, х <sub>2</sub> <sup>i</sup>,…, х<sub>n</sub><sup>i</sup>),(i =1,…) сходящихся от начального приближения `х ⁽⁰⁾=(х ₁⁰, х ₂⁰,…, х_n ⁰), к точному решению системы `х *=(х ₁*, х ₂*,…, х_n *).

Начальное приближение для решения системы `х ⁽⁰⁾ задается, исходя из физических особенностей решения задачи, известных решений близких задач либо других соображений.

Каждое текущее приближение `х <sup>( k+1 )</sup> строится на основе предыдущих. Правило для расчета `х ^{( k+1 )}(`х <sup>( k )</sup>, `х ^{( k- 1 )} ,...) называют расчетной схемой итерационного процесса.

Поскольку точное решение `х * неизвестно, то в качестве косвенной меры близости к нему принимают норму вектора разности двух последних приближений `х ^{( k+1 )}и `х <sup>( k )</sup>: Если она стремится к нулю и предел `х ^{( k+1 )} равен точному решению `х *, то такой итерационный процесс называют сходящимся. Его останавливают, когда рассмотренная норма становится меньше некоторого наперед заданного положительного числа e:

(7.1)

Если предел `х <sup>( k+1 )</sup> не существует либо существует, но не равен точному решению `х *, то такой итерационный процесс называют расходящимся.

Сходимость итерационного процесса к точному решению `х * зависит от удачного выбора начального приближения `х ⁽⁰⁾, а также от выбранной расчетной схемы процесса.

При наличии сходимости основным качественным показателем данных методов является скорость сходимости - число итераций, которое необходимо выполнить для получения решения заданной точности. Исследование сходимости итерационного процесса и оценка ее скорости являются центральными вопросами теории итерационных методов.

Данные методы решения систем линейных уравнений используют особенности хранения коэффициентов разреженных матриц. Поэтому для их реализации требуется меньшее количество вычислительных операций (около n ²) и соответствующих затрат машинного времени.

Важным преимуществом итерационных методов являются простота их алгоритмов, которые сводятся к расчету очередных приближений `х ^{( k+1 )} по расчетной схеме итерационного процесса, проверке условия (7.1) окончания процесса и, возможно, выполнению некоторых вспомогательных расчетов.

Также существенным преимуществом данных методов является отсутствие накопления погрешностей вычислений.

Рассмотрим наиболее простые из итерационных методов решения систем линейных уравнений - метод простой итерации (метод Якоби) и метод Зейделя.

Вопросы для проверки знаний.

1. Какие матрицы называют разреженными, какой метод хранения применяют для их элементов?

2. В чем заключается итерационный метод решения системы линейных уравнений?

3. Что называют расчетной схемой итерационного процесса?

4. Какие итерационные процессы называют сходящимся, а какие расходящимся?

5. По какой величине косвенно оценивают близость текущего приближенного решения к точному?

6. От чего зависит сходимость итерационного процесса к точному решению`?

7. Что называют скоростью сходимости итерационного процесса?

8. Каковы преимущества итерационных методов?

7.2. Метод последовательных приближений Якоби
(простой итерации)

Рассмотрим квадратную систему линейных уравнений порядка n:

(7.2)

Если в системе (7.2) диагональные элементы матрицы не равны 0 (a_ii ≠ 0, i = 1, 2, …, n), то можно выразить x ₁ из первого уравнения системы, x ₂ – из второго, …, x_n – из последнего уравнения n:

(7.3)

Полученную эквивалентную систему (7.3) используют для выполнения итерационного процесса следующим образом. Вначале задается начальное (нулевое приближение) искомого решения, которое обозначим как `х <sup>(0)</sup>. Подставляя вектор данных значений в правую часть (7.3), в левой части получим новые значения для вектора решений, которые обозначим как `х ⁽¹⁾. Подставляя `х <sup>(1)</sup> в правую часть (7.2), в левой получим следующее приближение `х ⁽²⁾ и т.д.

Таким образом, из (7.3) получены рекуррентные соотношения, позволяющие по текущему приближенному решению `х <sup>( k )</sup> получить следующее приближение `х ^{( k +1)}:

(7.4)

Соотношения (7.4) задают расчетную схему итерационного процесса, называемого методом простой итерации или методом Якоби.

Для косвенной оценки близости получаемого приближенного решения `х <sup>( k +1)</sup> к точному `х * используется условие (7.1) для нормы вектора разности между приближениями `х <sup>( k +1)</sup> и `х ^{( k )}: Оценка сходимости итерационного метода в общем случае представляет собой достаточно сложную задачу. Одним из простейших видов ограничений на вид матрицы системы, гарантирующих сходимость метода простой итерации к точному решению, является условие диагонального преобладания.

Достаточное условие сходимости метода простой итерации. Если для матрицы системы А выполнено условие диагонального преобладания во всех строках:

(7.5)

то итерационный процесс метода простой итерации сходится при любом выборе начального приближения `х ⁽⁰⁾.

В тех случаях, когда матрица системы уравнений не удовлетворяет условию диагонального преобладания (7.5), вопрос о сходимости метода остается открытым и его нужно исследовать другими методами.

Выбор начального приближения может существенно повлиять на количество итераций, необходимых для получения приближенного решения. Наиболее часто в качестве начального приближения `х ⁽⁰⁾ принимают вектор с компонентами х_i ⁽⁰⁾, равными:

1) b_i/a_ii (обычно используется в случае диагонального преобладания в матрице системы А) либо

2) 0 - для матриц других типов.

Пример 1. Решить систему линейных уравнений методом простой итерации с точностью e=0,1:

Для устранения ошибок вычислений все промежуточные результаты найти в рациональном виде. В конце расчета результат округлить с точностью до 4 знаков после запятой. Найти абсолютные и относительные погрешности найденных значений неизвестных.

Решение. Составляем на основе системы расчетную схему задачи:

Строки матрицы удовлетворяют условию диагонального преобладания. Выбираем начальное приближение `х ⁽⁰⁾:

х ₁⁽⁰⁾ = (-3)/(-4)= 3/4; х ₂⁽⁰⁾ = (-14)/4 = -7/2; х ₃⁽⁰⁾ = 9/2.

Итерация 1. Рассчитываем первое приближение `х <sup>(1)</sup>, находим норму разности `х ⁽¹⁾ - `х ⁽⁰⁾ и сравниваем ее с e:

.

Так как норма приращения вектора решения больше e, итерации необходимо продолжить.

Итерация 2. Рассчитываем второе приближение `х <sup>(2)</sup>, находим норму разности `х ⁽²⁾ - `х ⁽¹⁾ и сравниваем ее с e:

.

Так как норма приращения вектора решения больше e, итерации необходимо продолжить.

Итерация 3. Рассчитываем третье приближение `х <sup>(3)</sup>, норму разности `х ⁽³⁾ - `х ⁽²⁾ и сравниваем ее с e:

.

Так как норма приращения вектора решения меньше e, вычисления заканчиваем, принимая в качестве искомого итерационного решения:

х ₁^(и) = 129/128»1,0078; х ₂^(и) = (-195)/64» -3,0469; х ₃^(и) = 253/64» 3,9531.

Точное решение системы нетрудно найти, например, методом Гаусса:

х ₁ = 1; х ₂ = -3; х ₃ = 4.

Абсолютные погрешности неизвестных находим по формуле D х_i = ï х_i ^(и) - х_i ï:

D х ₁ » 0,0078;D х ₂» 0,0469; D х ₃ » 0,0469.

Относительные погрешности определяем по формуле d х_i = D х_i /ï х_i ï:

d х ₁ » 0,0078/1=0,0078;d х ₂» 0,0469/3» 0,0156; d х ₃ » 0,0469/4»0,0117.

Основным достоинством метода простой итерации является достаточно простая реализация. К недостаткам относится достаточно медленная сходимость.

Вопросы для проверки знаний.

1. Каким образом из системы линейных уравнений получают расчетную схему итерационного процесса метода Якоби?

2. В чем заключается условие диагонального преобладания и как на его основе формулируется достаточный признак сходимости итерационного метода Якоби?

итерационный метод решения системы линейных уравнений

Практическое задание.

1. Решить систему линейных уравнений методом простой итерации с точностью e=0,1:

Для устранения ошибок вычислений все промежуточные результаты найти в рациональном виде. В конце расчета результат округлить с точностью до 4 знаков после запятой. Найти абсолютные и относительные погрешности найденных значений неизвестных.