2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Решение СЛАУ методом простой итерации
Сообщение03.06.2011, 15:41 
Аватара пользователя


01/06/11
35
Волгоград
Дана система 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. Искал и в Интернете и в книгах примеры решения СЛАУ методом простой итерации, так и не смог найти. Везде только теория.

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение03.06.2011, 18:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 11:34 
Аватара пользователя


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

Напомню условия. Дана система:
$$ \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$. Так что в правильности решения сомневаться не приходится.
Спасибо за внимание.

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 12:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 12:16 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 13:07 
Заслуженный участник
Аватара пользователя


30/01/09
7124
M_a_Ge в сообщении #454264 писал(а):
мат-ламер, а какой метод тогда применяется? Ведь итерационных методов много.
Да и вообще как правильно выбрать метод решения СЛАУ?

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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 13:14 
Аватара пользователя


01/06/11
35
Волгоград
мат-ламер, спасибо за ответ.

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение05.06.2011, 14:49 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение11.11.2012, 10:31 


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение11.11.2012, 13:25 
Заслуженный участник
Аватара пользователя


30/01/09
7124
FenixGuard в сообщении #642826 писал(а):
Но у меня возникла проблема с решением вот такой системы уравнений: 2x^2-xy-5x+1=0 x+3lgx-y^2=0. как раз именно методом просто итерации.

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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение11.11.2012, 14:49 
Заслуженный участник


09/05/12
25179
FenixGuard в сообщении #642826 писал(а):
Всем доброго времени суток, почитал тему, очень все понятно написано,

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

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

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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение11.11.2012, 20:30 


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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение11.11.2012, 20:38 
Заслуженный участник


09/05/12
25179
FenixGuard в сообщении #643265 писал(а):
так может она решается методом ньютона?

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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение12.11.2012, 08:37 


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

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

 Профиль  
                  
 
 Re: Решение СЛАУ методом простой итерации
Сообщение12.11.2012, 20:06 
Заслуженный участник
Аватара пользователя


30/01/09
7124
FenixGuard в сообщении #643265 писал(а):
Хорошо пойдет от противного. Вот авторы книги Н. В. Копченова, И. А. Марон "Вычислительная математика в примерах и задачах" Москва 1972. Ну если вдруг кому интересно, то страница 95 Задача 1. Предшествующий материал к ней это метод простой итерации. Но как я уже заметил, там есть до метода простой итерации и метод ньютона, так может она решается методом ньютона? Подскажите?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group