- •Элементы линейной алгебры с приложением
- •Введение
- •1. Определители
- •Определителем матрицы Вназывается число
- •2. Системы линейных уравнений
- •Рассмотрим снова систему (2). Определитель
- •3. Векторы и ленейные операции над ними
- •4. Векторы в декартовой прямоугольной системе координат. Скаряное произведение
- •Доказательство.Используя свойства 3, 4, получим
- •5. Векторное и смешанное произведения
- •Легко проверить исходя из определения векторного произведения, что
- •6. Уравнение плоскости и прямой
- •Решение. Уравнение плоскости, проходящей через точку м1имеет вид
- •7. Матрицы
- •Пусть дана квадратная матрица
- •Покажем, что
- •8. Ранг матрицы. Исследование системы линейных уравнений
- •Рассмотрим матрицу
- •Матрицы
- •Пример 2. Решить систему
- •По формулам Крамера
- •9. Линейные преобразования. Собственные векторы
- •Матрица
- •Так как 0, то1,2,3– ненулевое решение однородной системы
- •В силу следствия из раздела 8
- •В двумерном случае система (3) имеет вид
- •Замечание.Если матрица Аφлинейного преобразованияв базе диагональная:
- •10. Симметрические и ортогональные матрицы Квадратная матрица вида
- •Оказывается, что векторы 1и2перпендикулярны. В самом деле, применяя лемму, получаем
- •Матрица
- •Матрица преобразования в базе1,2диагональная
- •11. Квадратичные формы. Кривые второго парядка
- •12. Положительные матрицы
- •13. Балансовая модель
- •14. Продуктивные матрицы
- •15. Норма матрицы
- •16. Итерационный метод
- •17. Возмущение решений
- •18. Демографический рост
- •19. Регрессионные модели
- •20. Постановка транспортной задачи
- •20.1 Математическая формулировка транспортной задачи.
- •20.2 Базисное распределение в транспортной задаче
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 11
- •21. Техника решения транспортной задачи вручную (метод потенциалов)
- •Вариант 13
- •22. Формализация производственных задач линейного программирования
- •23. Геометрическая интерпретация задач линейного программирования
- •24. Симплексный метод решения задач линейного программирования
- •24.1 Общая формулировка задачи линейного программирования
- •24.2 Заполнение симплексной таблицы по строкам
- •Симплексная таблица
- •24.3 Заполнение симплексной таблицы по столцам
- •24.4 Двойственные задачи, оценки, проблемы.
- •Ответы к вариантам:
- •25. Метод последовательных приближений (метод итерации)
- •26. Условия сходимости итерационного процесса
- •27. Оценка погрешности приближенного процесса метода итерации
- •28. Метод зейделя. Условия сходимости процесса зейделя
- •29. Оценка погрешности процесса зейделя
- •30. Привеление системы линейных уравнений к виду, удобному для итерации
- •31. Исправление элементов приближенной обратной матрицы
- •Задания для самостоятельной работы.
- •Вариант 1
- •Вариант 9
- •Экзаменационные вопросы
26. Условия сходимости итерационного процесса
Пусть дана приведённая к нормальному виду система линейных уравнений Х=+Х. Итерационный процесс и его сходимость зависят от величины элементов матрицы следующим образом:если сумма модулей элементов строк или сумма модулей элементов столбцов меньше единицы, то процесс итерации для данной системы сходится к единственному решению независимо от выбора начального вектора.
Следовательно, условия сходимости можно записать так:
<1 (i=1, 2, …,n ) или <1 (j=1, 2, …,n )
Пример 1. Для системы
или
Итерационный процесс сходится, так как
Аналогично можно было бы проверить выполнение условия сходимости, взяв суммы модулей элементов строк.
Процесс итерации заведомо сходится, если элементы матрицы удовлетворяют неравенству , где n- число неизвестных данной системы. В нашем примере n=3 и все элементы .
Сходимость итерационного процесса связана нормами матрицы следующими соотношениями. Если выполняется одно из условий:
либо
либо
то процесс итерации линейной системы сходится к единственному решению.
Так, в рассмотренном выше примере норма
т.е. итерационный процесс сходится.
27. Оценка погрешности приближенного процесса метода итерации
Если задана допустимая погрешность вычислений и- вектор точных значений неизвестных линейной системы, аестьk-e приближение значений неизвестных, вычисленное методом итерации, то для оценки погрешности метода применяется формула
(1)
где - одна из трех норм матрицы , - та же норма вектора , аk- число итераций, необходимое для достижения заданной точности. При этом предполагается, что последовательные приближения (гдеj=0, 1, …, k, i=1, 2, …, n) вычисляются точно, в них отсутствуют погрешности округления.
Пример 1. Показать, что для системы
итерационный процесс сходится, и определить, сколько итераций следует выполнить, чтобы найти корни системы с точностью до 10-4.
Решение. 1) Приводим систему к нормальному виду
или
2) Матрица системы
Используя норму , получаем Следовательно, итерационный процесс для данной системы сходится.
3) Имеем
4) Применяем формулу (1), находим
Теоретическая оценка числа итерации, необходимых для обеспечения заданной точности, практически оказывается завышенной.
28. Метод зейделя. Условия сходимости процесса зейделя
Метод Зейделя представляет собой некоторую модификацию метода последовательных приближений. В методе Зейделя при вычислений (k+1)-го приближения неизвестного xi учитываются уже найденные ранее (k+1)-е приближения неизвестных x1, x2, …,xi-1.
Пусть дана линейная система
(1)
Выбираем произвольно начальные приближения корней ,, …,и подставляем в первое уравнение системы (1):
полученное первое приближение подставляем во второе уравнение системы (1):
полученное первое приближение иподставляем в третье уравнение системы (1):
и т.д. Наконец,
Аналогично строим вторые, третьи и т.д. итерации.
Таким образом, предполагая, что k-е приближение корней известны, по методу Зейделя строим (k+1)-е приближение по следующим формулам:
…………………………………………..
где k=0, 1, 2, …, n.
Пример 1. Методом Зейделя решить систему
Решение. 1) Приведём систему к нормальному виду:
или
2) За нулевые приближения возьмём соответствующие значения свободных членов: =0,19;=0,97;= -0,14.
3) Строим итерации по методу Зейделя. Первые приближения:
=0,19+0,24∙0,19-0,05∙0,97-0,24∙(-1,4)=0,2207,
=0,97-0,22∙0.2207+0,09∙0,97-0.44∙(-0,14)=1,0703,
= -0,14+ 0,13∙0,2207-0,02∙1,0703+0,42∙(-0,14)=-0,1915.
Второе приближение:
=0,19+0,24∙0,2207-0,05∙1,0703-0,24∙(-0,1915)=0,2354
=0,97-0,22∙0,2354+0,09∙1,0703-0.44∙(-0,1915)=1,0988
= -0,14+ 0,13∙0,2354-0,02∙1,0988+0,428∙(-0,1915)=-0,2118
и т.д.
Решение этого примера приведено в табл.2.11.
Таблица 2.11
-
№ итерации
0
1
2
3
4
5
6
7
8
0,19
0,2207
0,2354
0,2424
0,2454
0,2467
0,2472
0,2474
0,2475
0,97
1,0703
1,0988
1,1088
1,1124
1,1138
1,1143
1,1145
1.1145
-0,14
-0,1915
-0,2118
-0,2196
-0,2226
-0,2237
-0,2241
-0,2243
-0,2243
Построение итерации заканчивается, когда с заданной степенью точности получаем одинаковые значения в двух итерациях подряд. В нашем примере это итерация 7 и 8.
Окончательный ответ: 0,248;1,114;-0,224
Процесс Зейделя для линейной системы Х=+Х так же, как и процесс последовательных приближений, сходится к единственному решению при любом выборе начального приближения, если какая-нибудь из норм матрицыменьше единицы, т.е. если
либо
либо
Процесс Зейделя сходится к единственному решению быстрее процесса простой итерации.
Пример 2. Проверить, сходится ли процесс Зейделя для системы, рассмотренной в примере 1.
Решение. 1) После приведения системы к нормальному виду (см. стр. 98) получаем матрицу
2) Находим
Следовательно, процесс итерации для данной системы сходится к единственному решению, несмотря на то, что