Метод простой итерации

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

Постановка задачи

Рассмотрим систему m линейных уравнений с n неизвестными:

Ее можно записать в матричном виде A x = B, где

Решить СЛУ – значит найти набор таких чисел , которые превращают уравнения в верные равенства.

СЛУ совместна, если она имеет хотя бы одно решение.

СЛУ несовместна (противоречива), если она не имеет решения.

Совместная СЛУ определенна, если она имеет единственное решение и неопределенна, если более одного решения.

СЛУ имеет единственное решение, если ранг матрицы A равен рангу расширенной матрицы (A|b): rang (A) = rang (A|b).

СЛУ имеет единственное решение, если rang (A) = n и бесконечно много решений, если rang (A) < n.

Если матрица A – квадратная и det(A)¹0, то она называется невырожденной.

СЛУ с n неизвестными, имеющими невырожденную матрицу A, совместна и имеет единственное решение.

Все численные методы решения СЛУ можно разделить на прямые, итерационные и вероятностные.

Прямые методы дают решение системы за конечное число арифметических операций.

Например, метод Крамера (метод определителей),

метод Гаусса (метод последовательного исключения неизвестных).

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

Например, метод простой итерации,

метод Зейделя.

Вероятностные методы носят общее название – методы Монте-Карло.

Метод простой итерации

Метод простой итерации решения СЛУ аналогичен методу решения уравнения с одной неизвестной методом простой итерации. Во втором случае уравнение F(х) = 0 заменяется равносильным x = f(x). Если последовательность приближений, или итерационная последовательность х₀, х₁, …, х_n, где x_n = f(x_n-1) для n = 1, 2, …, сходится, то предел последовательности является корнем уравнения.

Для решения системы уравнений также необходимо привести её путем равносильных преобразований к системе вида:

или в сокращенной записи:

(i = 1, 2, …, n).

О системе с такой структурой говорят, что она «приведена к нормальному виду». Пользуясь ей, можно построить итерационную последовательность приближенных решений аналогично методу простой итерации для уравнения с одной переменной: х⁽⁰⁾, х^(1), …, х^(n), … - последовательность точек n-мерного пространства. При определенных условиях итерационная последовательность сходится к решению системы. Решение этого вопроса зависит от способа метризации пространства, то есть от определения расстояния между его двумя точками.

Функцию r (x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если

1) r (x,y)³0

2) r (x,y)=0 «x=y

3) r (x,y)= r (y,x)

4) r (x,y)£ r (x,z)+ r (z,y).

Множество X с введенной метрикой r назовем метрическим пространством.

Последовательность точек метрического пространства называется фундаментальной, если .

Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Отображение F пространства E в себя называется сжимающим, если . Данное условие называется условием Липшица.

x – неподвижная точка, если F(x)=x.

Рассмотрим 3 типа метрики.

Пусть x(x₁,x₂,…,x_n) и y(y₁,y₂,…,y_n) – две точки n -мерного пространства.

I. Максимальная из сумм модулей коэффициентов при неизвестных в правой части системы, взятых по строкам, должна быть меньше единицы:

II. Максимальная из сумм модулей коэффициентов при неизвестных в правой части системы, взятых по столбцам, должна быть меньше единицы:

III. Корень квадратный из суммы квадратов коэффициентов при неизвестных в правой части системы, должен быть меньше единицы: . Эта метрика называется также евклидовой.

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

Теорема. Пусть отображение F является сжимающим на полном метрическом пространстве с коэффициентом сжатия 0 £ a < 1, то есть r (Fx,Fy) < a r(x, y) для всех x, y из X. Тогда:

1) На X существует и притом ровно одна неподвижная точка x * из X (неподвижная означает Fx * = x *).

2) Решение x * равно пределу итерационной последовательности х_n точек из Х, определяемой рекуррентной формулой

x_n+1 = F(x_n), n = 0,1,2…,

где х₀ – произвольный элемент из Х.

3) При каждом n справедливо равенство

.

Итак, в условиях теоремы Банаха имеем следующее. Во-первых, уравнение x = F(x) обязательно имеет решение x * Î Х, причем единственное на этом множестве. Во-вторых, рекуррентная формула x_n+1 = F(x_n) определяет последовательность приближений к решению x *, при этом за начальное приближение х ₀ можно взять любой элемент из Х. В-третьих, если решение x * заменить приближенным значением x_n, то абсолютную погрешность приближения x_n можно вычислить по одной из следующих формул:

; .

Из последних соотношений следует, что для приближенного решения x_n с точностью e > 0 необходимо добиться выполнения хотя бы одного из неравенств

или .

Из неравенства в теореме Банаха видно, что от величины коэффициента сжатия зависит скорость сходимости итерационной последовательности. Чем меньше a, тем быстрее можно достичь желаемой точности приближенного решения.

Учитывая все сказанное, можно заключить, что теорема Банаха фактически дает метод уточнения приближенного решения СЛУ – метода итерации. Этот метод применим не только к решению систем линейных уравнений, но и к уравнениям вида x = F(x). Он привлекателен тем, что порождает процесс однотипных вычислений и нечувствителен к небольшим ошибкам.

Для практического применения метода итераций необходимо преобразовать систему линейных уравнений таким образом, чтобы по одной из метрик выполнялось α < 1.

Существуют разные приемы преобразования системы к такому виду, например, путем вычленения единицы из каждого диагонального коэффициента или деления уравнения на соответствующие диагональные коэффициенты.

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

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

Эти способы можно применять как в целом к системе, так и к отдельным уравнениям, переставляя, при необходимости, уравнения системы.

При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы.

Чтобы привести СЛУ к итерационному виду нужно:

1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);

2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.

Если для этой системы α < 1, то система задает сжимающее отображение.

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

Заметим также, что после каких-то преобразований условия будут выполняться, после каких-то – нет. Вполне возможно, что для некоторой конкретной системы метод итераций окажется неприемлем.

Рассмотрим на примере:

Решим систему трех линейных уравнений с тремя неизвестными методом простой итерации с точностью e = 10^-4.

2,34 х ₁ – 4,21 х ₂ – 11,61 х ₃ = 14,41

8,04 х ₁ + 5,22 х ₂ + 0,27 х ₃ = -6,44

3,92 х ₁ – 7,99 х ₂ + 8,37 х ₃ = 55,56

Сначала получим систему с преобладающими диагональными коэффициентами. Для этого в качестве первого уравнения возьмем второе, третьего – первое, второго – сумму первого и третьего уравнений:

8,04 х ₁ + 5,22 х ₂ + 0,27 х ₃ = - 6,44

6,26 х ₁ – 12,20 х ₂ – 3,24 х ₃ = 69,97

2,34 х ₁ – 4,21 х ₂ – 11,61 х ₃ = 14,41.

Разделим теперь каждое уравнение на свой диагональный коэффициент и выразим из каждого уравнения диагональное неизвестное:

х ₁= - 0,649 х ₂ - 0,0,34 х ₃ - 0,801

х ₂ = - 0,513 х ₁ – 0,266 х ₃ – 5,735

х ₃ = 0,202 х ₁ – 0,363 х ₂ – 1,241.

Теперь необходимо проверить, будет ли отображение сжимающим, то есть выполняются ли условия сходимости. Попробуем установить сходимость по метрике r₂. Заметим, что максимальной суммой модулей коэффициентов по столбцам будет сумма модулей коэффициентов при х ₂. однако и она не удовлетворяет нужному условию: 0,649 + 0,363 = 1,012 > 1.

Невыполнение одного из условий еще не означает, что метод итераций применить нельзя. Попробуем установить сходимость в пространстве с метрикой r₃. Имеем: 0,649² + 0,034² +0,513² + 0,266² + 0,202² + 0,363² =0,422 + 0,001 + 0,263 + 0,071 + 0,041 + 0,131 = 0,929 < 1.

Итак, итерационный процесс сходится, причем a = Ö0,929» 0,93. для достижения точности e = 10^-4. приближения нужно находить до тех пор, пока не будет выполнено неравенство .

Поскольку a близко к единице, то скорость сходимости в данном случае будет невелика.

Само решение можно выполнить различными средствами: программным или с использованием математических пакетов.

Поиск по сайту: