2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Метод Простых Итераций (СЛАУ)
Сообщение20.09.2007, 09:41 


20/09/07
2
Новосибирск
помогите справиться с задачей, преподаватель дал на одной из лекций, неделю бьюсь над ней а решить не получается:
Нужно доказать, что метод простых итераций сходится не только в случае, если выполняется условие диагонального преобразования по строкам, но и в случае, если выолняется условие диагонального преобразования по столбцам.
При делении на диагональные элементы строки, на главное диагонале появляются единицы, и при выписке матрицы С заместо всех единиц записываются нули, а главное условие сходимости МПИ является условие что норма С меньше единицы! очень буду благодарен любой помощи по доказательству

 Профиль  
                  
 
 Re: Метод Простых Итераций
Сообщение20.09.2007, 10:06 
Заслуженный участник
Аватара пользователя


23/08/07
4639
Нов-ск
Splinter писал(а):
Нужно доказать, что метод простых итераций сходится не только в случае, если выполняется условие диагонального преобразования по строкам, но и в случае, если выолняется условие диагонального преобразования по столбцам.

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

 Профиль  
                  
 
 
Сообщение20.09.2007, 14:29 


20/09/07
2
Новосибирск
решается обычная СЛАУ из трех уравнений
метод простых итераций , один из методов решения СЛАУ, строки делятся на диагональный элемент главное диагонали, после чего составляется матрица 3 на 3 и матрица-столбец, в матрице 3 на 3 при выписывании её заместо единиц ставится ноль, 4 столбец матрицы A явлется матрицей-столбцом и обзавем его B, далее идет вычисления по формуле X^(K+1) = B - C*X^K, главное условие сходимости это то, что норма матрицы 3 на 3 ||C|| < 1, считается она таким образом: максимальное из C12+C13, C21+C23 и C31+C32 таким образом получается что ||C|| действительна больше всех остальных сумм, и по необходимому условию должна быть меньше единицы, иначе матрица расходится за N-ое количество шагов, так вот это диагональное преобразование по строкам дальше можно доказать что матрица сходится при конечном количестве шагов, но к сожалению я не умею писать формулы, так что сразу прошу прощения за столь кривое написание формул. Вот у нас получилось диагональное преобразование по строкам, а надо по столбцам, да так что бы норма взятая по столбцам тоже была меньше единицы и доказать что она должна быть меньше единицы чтобы матрица сходилась.
вообще не очень из меня учитель, обьяснять я не умею:(

 Профиль  
                  
 
 
Сообщение20.09.2007, 18:36 
Заслуженный участник
Аватара пользователя


01/08/06
2417
Уфа
Помогу правильно сформулировать задачу.
Дана СЛАУ ${\bf Ax = b}$, где:
$${\bf A} = \left(\begin{array}{ccc}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}\\
a_{31}&a_{32}&a_{33}
\end{array}\right)$$,
$${\bf b} = \left(\begin{array}{c}b_1\\b_2\\b_3\end{array}\right)$$,
$${\bf x} = \left(\begin{array}{c}x^1\\x^2\\x^3\end{array}\right)$$ (неизвестное решение СЛАУ),

Причём известно, что $|a_{11}| > |a_{12}|+|a_{13}|$, $|a_{22}| > |a_{21}|+|a_{23}|$, $|a_{33}| > |a_{31}|+|a_{32}|$. Это свойство матрицы называется диагональным преобладанием по строкам, обратите внимание: не преобразованием, а преобладанием.
Преобразуем исходную систему следующим образом: поделим каждое уравнение на соответствующий диагональный элемент: 1-е уравнение (т.е. строку $(a_{11}\ a_{12}\ a_{13})$ и компонент правой части $b_1$) поделим на $a_{11}$, 2-е уравнение --- на $a_{22}$, 3-е уравнение --- на $a_{33}$. В результате получится какая-то другая матрица (назовём её ${\bf A'}$), у которой единицы на главной диагонали ($a'_{ii}=1$), и какой-то другой вектор правой части (${\bf b'}$). (на занятиях вы для удобства рассматривали расширенную матрицу 3x4, полученную простым приписыванием к матрице ${\bf A}$ вектора ${\bf b}$ справа, но это не меняет сути дела, просто мне привычнее рассматривать их отдельно).
Далее. На лекциях вы рассматривали метод простой итерации, который состоит в том, что выбирается какое-то начальное приближение ${\bf x_0}$ (это тоже вектор, состоящий из компонентов $x_0^1$, $x_0^2$, $x_0^3$). И каждое следующее приближение строится по следующей формуле: ${\bf x_{n+1}}={\bf b'}-{\bf Cx_n}$, где ${\bf C=A'-E}$, ${\bf E}$ --- единичная матрица. Поскольку у матрицы ${\bf E}$ также единицы на главной диагонали (как и у ${\bf A'}$), то их разность ${\bf C}$ будет иметь на главной диагонали нули.
Также на лекциях вы доказывали теорему, что при указанных условиях построенный итерационный процесс сходится к точному решению СЛАУ. Доказательство строится на лемме о сжимающем отображении, которая, в свою очередь, опирается на тот факт, что $||{\bf C||$ (норма матрицы ${\bf C}$) строго меньше 1.
Поэтому вопросы стоят так:
(1) Почему $||{\bf C||$ меньше 1? (это должно было быть у вас в лекциях, на это опирается доказательство)
(2) Почему $||{\bf C||$ будет меньше 1 и в том случае, когда у исходной матрицы ${\bf A}$ будет диагональное преобладание не по строкам, как было у вас на лекции, а по столбцам? Т.е. в том случае, когда $|a_{11}| > |a_{21}|+|a_{31}|$, $|a_{22}| > |a_{12}|+|a_{32}|$, $|a_{33}| > |a_{13}|+|a_{23}|$. Это именно то, что нужно доказать Вам.

Всё, что я до этого сделал --- это просто сформулировал задачу, используя правильные термины, не более. Учитесь правильно формулировать задачу, иначе Вас никто не поймёт!

Как доказать (2)? Во-первых, внимательно посмотреть на доказательство (1) у Вас в конспекте лекций и понять его, и во-вторых, попытаться действовать по аналогии.

 Профиль  
                  
 
 
Сообщение21.09.2007, 11:00 
Заслуженный участник
Аватара пользователя


23/08/07
4639
Нов-ск
СЛАУ ${\bf Ax = b}$ записана как $\bf x = \bf Cx + b_1$,
где сумма модулей элементов в каждом столбце матрицы $\bf C $ не превосходит $q < 1$.

Получается итерационный метод $\bf x^{n+1} = \bf Cx^n + b_1$
и соотношение $\bf y^{n+1} = \bf Cy^n$ для погрешности $\bf y^{n} = \bf x^n -\bf x^*$.

Тогда $\sum_i {|y^{n+1}_i|} = \sum_i |{\sum_j c_{ij} y^{n}_j|} \le   \sum_i {\sum_j |c_{ij}| |y^{n}_j|} <   q \sum_j {|y^{n}_j|}$,
что и означает линейную сходимость со знаменателем $ q $.

 Профиль  
                  
 
 Re: Метод Простых Итераций (СЛАУ)
Сообщение15.12.2011, 02:21 


15/12/11
1
А не подскажете, как быть если система не приведена к диагональному преобладанию, заранее большое спасибо))

 Профиль  
                  
 
 Re: Метод Простых Итераций (СЛАУ)
Сообщение15.12.2011, 12:27 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
 i  Тема перенесена в раздел "Численные методы" из "Высшей алгебры"

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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