Решение СЛАУ методом простой итерации

[M_a_Ge]

Дана система 4 линейных уравнений:

$$\begin{matrix} 2x_1 - &8x_2& -&3x_3& -&2x_4& &=& -18 \\ x_1 - &2x_2& + &3x_3& - &2x_4& &=& 28 \\ &x_2& +&x_3& + &x_4& &=& 10 \\ &11x_2& + &x_3& +&2x_4& &=& 21 \\ \end{matrix}$$

Нужно найти решение системы уравнений методом простой итерации с с точностью до $\bf 10^{-4}$.

--------------------
Решение:
1. Выяснить являются ли преобладающими диагональные элементы. Если я правильно понял, то в этой системе нет преобладающих диагональных элементов по строкам для $x_1, x_3, x_4$. Что делать, как преобразовать систему?
2. Привести систему уравнений к нормальному виду, разрешив ее относительно диагональных неизвестных.
Я получил следующую систему нормально вида (правильно?):

$$\begin{matrix} x_1 &=& 4x_2 + 1,5x_3 - x_4 &-& 9 \\ x_2 &=& 0,5x_1 + 1,5x_3 - x_4 &-& 14 \\ x_3 &=& -x_2 - x_4 &+& 10 \\ x_4 &=& -5,5x_2 - 0,5x_3 &+& 10,5 \end{matrix}$$

3. Теперь нужно убедиться в том, что полученная нормальная система удовлетворяет условиям сходимости итерационного процесса. Для этого вычислим:

$$\sum_{k=1}^4 | a_{1k}| = 15,5; \; \sum_{k=1}^4 | a_{2k}| = 17; \; \sum_{k=1}^4 | a_{3k}| = 12; \; \sum_{k=1}^4 | a_{4k}| = 16,5; \; $$

$$\max_i \sum_{k=1}^4 | a_{ik}| = 17 > 1;$$

Это говорит о том, что я ошибся уже в первом шаге и неправильно привел систему к нормальному виду.

Определитель матрицы равен 105, т.е. система имеет единственное решение. Подскажите как правильно привести систему к нормальному виду.

P.S. Искал и в Интернете и в книгах примеры решения СЛАУ методом простой итерации, так и не смог найти. Везде только теория.

[мат-ламер]

Можете попробовать поменять нумерацию переменных и переставить местами уравнения. Вдруг поможет.

[M_a_Ge]

Я разобрался с этим методом. Далее привожу подробное решение данной системы, чтобы ищущие в поисковой системе примеры решения СЛАУ методом простых итераций, могли наглядно увидеть как решаются подобные задания.

Напомню условия. Дана система:

$$ \begin{matrix} 2x_1 - &8x_2& - &3x_3& - &2x_4& &=& -18 \\ x_1 - &2x_2& + &3x_3& - &2x_4& &=& 28 \\ &x_2& + &x_3& + &x_4& &=& 10 \\ &11x_2& + &x_3& + &2x_4& &=& 21 \\ \end{matrix} $$

Нужно найти решение системы уравнений методом простой итерации с с точностью до $\bf 10^{-4}$.
--------------------
Решение:
Определитель данной системы равен $\det(A) = 105$, значит существует единственное решение данной системы.
1. Выяснить являются ли преобладающими диагональные элементы. Это очень важный шаг, проверяется условие сходимости этого метода. Нужно чтобы оно выполнялось.
Что значит преобладающие элементы? Это значит, что рассматриваемый коэффициент при неизвестной по модулю должен быть больше суммы элементов других коэффициентов при неизвестных. Например, в нашей системе только один явно преобладающий элемент по строке для $x_2$:

$$ |11| > |1| + |2| \Leftrightarrow 11 > 3 $$

Для $x_1, x_3, x_4$ это условие не выполняется. Значит нам нужно преобразовать нашу систему, чтобы это условие выполнялось. Как это сделать? Смотрите.

$$ \begin{matrix} 2x_1 - &8x_2& - &3x_3& - &2x_4& &=& -18 &(A)& \\ x_1 - &2x_2& + &3x_3& - &2x_4& &=& 28 &(B)& \\ &x_2& + &x_3& + &x_4& &=& 10 &(C)& \\ &11x_2& + &x_3& + &2x_4& &=& 21 &(D)& \\ \end{matrix} $$

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

$$ \begin{array} {lcr} A_1 = (A+B) - (C+D) \\ B_1 = D \\ C_1 = B + 2C \\ D_1 = (3C - D) - B \\ \end{array} $$

Получилась система эквивалентная исходной:

$$\begin{matrix} 3x_1 - 3x_4 &=& 21 &(A_1)& \\ 11x_2 + x_3 + 2x_4 &=& 21 &(B_1)& \\ x_1 + 5x_3 &=& 48 &(C_1)& \\ -x_1 + 2x_2 +7x_3 + 11x_4 &=& 61 &(D_1)& \\ \end{matrix}$$

Преобразовывая систему, я старался избавиться от малых коэффициентов при неизвестных, чтобы коэффициент при выбранной неизвестной преобладал. Будьте внимательны при преобразовании, любая допущенная ошибка на этом шаге сделает все последующие операции бессмысленными.
2. Привести систему уравнений к нормальному виду, разрешив ее относительно диагональных неизвестных. Итак, когда мы убедились, что диагональные элементы преобладают, то можно преобразовать систему к нормальному виду, т.е. сейчас у нас система вида $\bf Ax =b $, где $A$ - матрица коэффициентов при неизвестных, $b$ - свободные члены. А нам нужна система вида

$$ \bf x_i = \beta_i + \sum_{j=1}^na_{ij}x_j $$

где $ \bf \beta_i = b_i/a_{ii}$, \bf $a_{ij} = - a_{ij}/a_{ii}$, причем нужно убедиться что $ a_{ii} \not= 0 $.

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

$$\begin{array}{lcr} x_1 = x_4 + 7 \\ x_2 = -0,09091x_3 - 0.18182x_4 + 1,90909 \\ x_3 = -0,2x_1 + 9,6 \\ x_4 = 0,09091x_1 - 0,18182x_2 - 0,63636x_3 + 5,54545 \\ \end{array}$$

Так как заданная точность должна быть в пределах 4-х знаков, я округлял все значения до 5-и знаков. Будьте внимательны со знаками, можно легко ошибиться. К примеру, почему в первом уравнении $x_4$ положителен? А вот почему: $-(-3/3) = 1$ (см. формулу выше). Если бы коэффициент при $x_1$ был бы отрицательным, то тогда $x_4$ был бы тоже отрицательным, так как $-(-3/-3) = -1$.
3. Теперь нужно убедиться в том, что полученная нормальная система удовлетворяет условиям сходимости итерационного процесса. Для этого вычислим:

$$\sum_{k=1}^4|a_{1k}| = 1; \; \sum_{k=1}^4|a_{2k}| = 0,27273; \; \sum_{k=1}^4|a_{3k}| = 0,2; \; \sum_{k=1}^4|a_{4k}| = 0,90909;$$

$$\max_i\sum_{k=1}^4|a_{ik}| = 1 \geq 1$$

Можно приступать к вычислениям.
4. Вычисление решения системы уравнений. Теперь все готово для непосредственного нахождения корней. В качестве начального приближения принято выбирать вектор свободных членов, так и поступим.

Итерация №1:
Подставляем вместо неизвестным в системе нормального вида соответствующие им свободные члены:

$$\begin{array}{lcr} x_1 = 5.54545 + 7 = \fbox{12,54545}\\ x_2 = -0,09091 \times 9,6 - 0.18182 \times 5,54545 + 1,90909 = \fbox{0,02808} \\ x_3 = -0,2 \times 7 + 9,6 = \fbox{8,2} \\ x_4 = 0,09091 \times 7 - 0,18182 \times 1,90909 - 0,63636 \times 9,6 + 5,54545 = \fbox{-0,27435} \\ \end{array}$$

Итерация №2:
Теперь подставляем в систему нормального вида полученные значения неизвестных из предыдущей итерации, получаем:
$\begin{array}{lcr} x_1 = 6,75656\\ x_2 = 1,21351 \\ x_3 = 7,09091 \\ x_4 = 1,4627 \\ \end{array}$
Продолжаем итерационный процесс пока не будет достигнута необходимая точность. Для нашей системы она равна $\varepsilon = 10^{-4} = 0,0001$
..........................
Итерация №18:
$\begin{array}{lcr} x_1 = 8,00016\\ x_2 = 0,999965 \\ x_3 = 7,99996 \\ x_4 = 1,0000809 \\ \end{array}$

Итерация №19:
$\begin{array}{lcr} x_1 = \fbox{8,0000809}\\ x_2 = \fbox{0,999979} \\ x_3 = \fbox{7,999968} \\ x_4 = \fbox{1,0000692} \\ \end{array}$
Требуемая точность достигнута, т.к. $|8,0000809 - 8,00016| < \varepsilon \Leftrightarrow 0,0000791 < 0,0001$ (это условие выполняется и для других неизвестных).

Видно что $x_1$ стремится к 8, $x_2$ к 1, $x_3$ к 8 и $x_4$ к 1. Таким образом, полученные на итерации №19 корни можно считать решением системы.

Немного о методе простой итерации. Метод простой итерации или метод Якоби применяется для нахождения корней системы линейных уравнений с заданной точностью. Этот метод используется для разряженных систем (у которых большинство элементов матрицы равны 0) или для систем большой размерности с преобладающими диагональными элементами.

Возможно Вам будет интересно почитать тему о доказательстве условия сходимости Метода Простых Итераций (СЛАУ).

P.S. Я решил эту систему методом Гаусса, корни равны $x_1=8$, $x_2=1$, $x_3=8$ и $x_4=1$. Так что в правильности решения сомневаться не приходится.
Спасибо за внимание.

[мат-ламер]

M_a_Ge. Тут дело в том, что на практике такие системы таким методом никто решать не будет. Попробуйте, например, запрограммировать первый шаг Ваших рассуждений. Многие системы, встречающиеся на практике, симметричные и положительно определённые, что снимает вопрос о диагональном преобладании.

[M_a_Ge]

мат-ламер, а какой метод тогда применяется? Ведь итерационных методов много.
Да и вообще как правильно выбрать метод решения СЛАУ?

[мат-ламер]

M_a_Ge в сообщении #454264 писал(а):

мат-ламер, а какой метод тогда применяется? Ведь итерационных методов много.
Да и вообще как правильно выбрать метод решения СЛАУ?

А я знаю? В Матлабе есть функция для решения произвольной (не обязательно симметричной) системы методом сопряжённых градиентов (по-моему, методом бисопряжённых градиентов). На практике исходную систему подвергают преобразованию (предобуславливание), чтобы уменьшить обусловленность. Дальше для симметричных пол. опр. систем можно применять метод сопряженных градиентов, например. Если есть информация о границах спектра, то можно применять и более сложные методы (например, метод чебышевского ускорения). А вообще в Матлабе есть косая черта, которая сама решает, какой метод применять.

[M_a_Ge]

мат-ламер, спасибо за ответ.

[M_a_Ge]

Кстати говоря, сейчас решил эту систему методом Зейделя. Сходимость этого метода в 3 раза превосходит метод Якоби (я достиг требуемой точности за 6 итераций). Если есть выбор, выбирайте метод Зейделя.

[FenixGuard]

Всем доброго времени суток, почитал тему, очень все понятно написано, не то что в этих книгах, одна теория и стандартные примеры! Но у меня возникла проблема с решением вот такой системы уравнений: 2x^2-xy-5x+1=0 x+3lgx-y^2=0. как раз именно методом просто итерации. Помогите пожалуйста разобраться. Спасибо!

[мат-ламер]

FenixGuard в сообщении #642826 писал(а):

Но у меня возникла проблема с решением вот такой системы уравнений: 2x^2-xy-5x+1=0 x+3lgx-y^2=0. как раз именно методом просто итерации.

Любопытно, есть ли в хоть одном учебнике совет решать такого рода системы методом простой итерации? Я сомневаюсь.

[Pphantom]

FenixGuard в сообщении #642826 писал(а):

Всем доброго времени суток, почитал тему, очень все понятно написано,

Только, к сожалению, не для Вашего случая. Все, что было выше, касается систем линейных уравнений, а у Вас они таковыми не являются.

мат-ламер в сообщении #642895 писал(а):

Любопытно, есть ли в хоть одном учебнике совет решать такого рода системы методом простой итерации?

-
Иногда так называют и тривиальный метод решения САУ путем сведения системы к виду $X=f(X)$, где $X$ - вектор неизвестных. По-видмому, нечто подобное автору вопроса и требуется реализовать.

[FenixGuard]

Хорошо пойдет от противного. Вот авторы книги Н. В. Копченова, И. А. Марон "Вычислительная математика в примерах и задачах" Москва 1972. Ну если вдруг кому интересно, то страница 95 Задача 1. Предшествующий материал к ней это метод простой итерации. Но как я уже заметил, там есть до метода простой итерации и метод ньютона, так может она решается методом ньютона? Подскажите?

[Pphantom]

FenixGuard в сообщении #643265 писал(а):

так может она решается методом ньютона?

Да, решается.

[TR63]

M_a_Ge в сообщении #454323 писал(а):

Кстати говоря, сейчас решил эту систему методом Зейделя. Сходимость этого метода в 3 раза превосходит метод Якоби (я достиг требуемой точности за 6 итераций). Если есть выбор, выбирайте метод Зейделя.

Только не забудьте, что при исследовании вопроса о сходимости итерационного процесса, в учебниках предлагается использовать теорему Гурвица, которая ложна.

[мат-ламер]

FenixGuard в сообщении #643265 писал(а):

Хорошо пойдет от противного. Вот авторы книги Н. В. Копченова, И. А. Марон "Вычислительная математика в примерах и задачах" Москва 1972. Ну если вдруг кому интересно, то страница 95 Задача 1. Предшествующий материал к ней это метод простой итерации. Но как я уже заметил, там есть до метода простой итерации и метод ньютона, так может она решается методом ньютона? Подскажите?

Попытки решения этой задачи методом простой итерации это шаманство. Возможно какие-то пляски с бубном помогут. Вычислительная математика разрабатывается вообщем-то для компьютеров, а не для шаманов. Что касается метода Ньютона, то если Вам повезёт с выбором начальной точки, то всё будет хорошо. Нужна ли Вам компьютерная программа, которая будет работать, если повезёт?