Итерационные методы решения систем линейных алгебраических уравнений
Применение приближенных (численных) способов нахождения корней системы матричных уравнений с большим числом неизвестных. Содержание методов простых итераций, Зейделя, релаксации, используемых в решении уравнений. Теорема сходимости итерационного процесса.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 21.09.2017 |
| Размер файла | 62,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
на тему: "Итерационные методы решения систем линейных алгебраических уравнений"
Введение
Пусть дана система линейных алгебраических уравнений (СЛАУ) вида:
(4.1)
Вводя в рассмотрение матрицы:
, , (4.2)
систему (4.1) можно записать в виде матричного уравнения:
. (4.3)
Для решения систем линейных алгебраических уравнений существуют точные методы: метод Гаусса, с помощью обратной матрицы (матричный метод), по формулам Крамера. Однако, при большом числе неизвестных применение точных методов решения затруднено. В этом случае для нахождения корней системы (4.1) целесообразнее пользоваться приближенными (численными) методами, которые и будут рассмотрены в данной главе.
§1. Метод простых итераций для решения систем линейных алгебраических уравнений
Пусть дана система линейных алгебраических уравнений вида (4.1).
Предположим, что диагональные элементы матрицы не равны нулю, т.е. (в случае равенства одного или нескольких из них нулю, с помощью перестановки уравнений или других эквивалентных преобразований можно добиться, чтобы они были отличны от нуля). Разделив -ое уравнение системы на , получим:
(4.4)
где коэффициенты:
при .
Введем обозначения:
, (4.5)
Тогда система (4.4) примет вид:
(4.6)
Систему (4.6) будем решать методом последовательных приближений. Выбираем начальное приближение ; далее вычисляем следующие приближения:
, ,…, , … (4.7)
Если последовательность приближений является сходящейся, т.е. у нее существует предел
,
то этот предел является решением системы (4.6). Действительно,
.
Получили:
,
т.е. - является решением системы (4.6), а система (4.6) получена из системы (4.1), следовательно, будет являться решением исходной системы (4.1).
Теорема 4.1 (достаточное условие сходимости итерационного процесса). Если для приведенной системы:
выполнено хотя бы одно из условий:
а)
б) ,
то процесс итерации, заданный формулой:
,
сходится к единственному решению этой системы, независимо от выбора начального приближения.
В частности процесс итерации заведомо сходится, если элементы приведенной системы (4.4) удовлетворяют неравенству:
,
где - число неизвестных системы.
Следствие. Для исходной системы (4.1) итерационный процесс сходится, если выполнены неравенства:
(то есть модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов, не считая свободных членов).
Теорема 4.2 (необходимое и достаточное условие сходимости процесса итерации для системы линейных уравнений).
Для сходимости процесса итераций:
при любом выборе начального приближения и любом свободном члене необходимо и достаточно, чтобы собственные значения матрицы (т.е. корни характеристического уравнения ) были по модулю меньше единицы.
Приведение исходной системы к виду, удобному для применения сходящегося итерационного процесса.
Теорема сходимости итерационного процесса накладывает жесткие условия на коэффициенты системы (4.3). Однако, если , то с помощью элементарных преобразований системы (4.3) ее можно заменить эквивалентной системой:
,
такой, что условия теоремы сходимости будут выполнены.
Умножим левую и правую часть соотношения (4.3) слева на матрицу , где - матрица с малыми по модулю элементами.
Проведем преобразования:
Если обозначить:
, ,
то получим:
.
Если элементы матрицы достаточно малы по модулю, т.е. , то элементы матрицы будут удовлетворять достаточному условию сходимости итерационного процесса.
Итерационный процесс заканчивается, если для двух приближений и выполнено условие:
,
где - заданная точность.
§2. Метод Зейделя
Размещено на http://www.allbest.ru/
Метод Зейделя представляет собой некоторую модификацию метода простых итераций. Основная его идея состоит в том, что при вычислении -го приближения неизвестной учитываются уже вычисленные ранее -е приближения неизвестных . Т.е. найденное -е приближение сразу же используется для получения -го приближения последующих координат (Рис. 4.1).
Предполагая, что -е приближения корней системы (4.4) известны, -е приближения корней будут находиться по следующим итерационным формулам метода Зейделя:
. (4.8)
Теорема 4.3 (достаточное условие сходимости метода Зейделя).
Если для приведенной системы:
выполнено хотя бы одно из условий:
1) , где ;
2) , где ;
3) , где ,
то процесс Зейделя сходится к единственному решению системы при любом выборе начального вектора.
Запишем систему (4.8) в сокращенном виде:
(4.9)
Введем обозначения:
,
, .
Тогда формулу (4.9) можем переписать в матричном виде:
, (4.10)
, , .
Теорема 4.4 (необходимые и достаточные условия сходимости метода Зейделя).
Для сходимости процесса Зейделя, заданного формулой (4.9), для приведенной системы линейных уравнений (4.4) при любом выборе свободного члена и начального вектора необходимо и достаточно, чтобы все корни уравнения были по модулю меньше единицы.
Пример 4.1. Построить рабочие формулы метода простых итераций и метода Зейделя для численного решения СЛАУ вида:
(4.11)
Решение. Заметим, что система (4.11) имеет точное решение .
Из системы (4.11) видно, что модули диагональных коэффициентов в каждом уравнении отличны от нуля и больше суммы модулей всех остальных коэффициентов, не считая столбца свободных членов. Тогда, разделим каждое уравнение системы (4.11) на соответствующий диагональный коэффициент, сформируем столбец в левой части и перенесем остальные слагаемые в правую часть и получим рабочие формулы метода простых итераций вида:
Начальное приближение обычно выбирают равным столбцу свободных членов преобразованной системы .
Рабочие формулы метода Зейделя запишутся так:
§3. Метод релаксации
Рассмотрим систему линейных алгебраических уравнений (4.1), в которой .
Сделаем преобразования: для этого свободные члены перенесем в левую часть и каждое -тое уравнение поделим на . Таким образом, получим систему, удобную для релаксации:
(4.12)
.
Введем понятие невязки для приближенного решения . Пусть дана система , тогда точное решение можно записать в виде:
,
- правка корня . Подставим:
в систему, получим:
Введем обозначение:
.
.
- выражение называется невязкой для приближенного решения .
Пусть задано начальное приближение системы (4.12):
.
Подставим данное приближение в систему (4.12) и получим невязки : итерация решение матричное уравнение
(4.13)
Если одной из неизвестных дать приращение , то соответствующая невязка уменьшится на величину , а все остальные невязки изменятся на величину . Чтобы обратить очередную невязку в нуль, нужно величине дать приращение , следовательно, , а остальные невязки будут равны:
.
Метод релаксации (метод ослабления) заключается в том, что на каждом шаге обращают в нуль максимальную по модулю невязку путем изменения значения соответствующей компоненты приближения. Процесс заканчивается, когда все невязки последней преобразованной системы будут равны нулю с заданной точностью.
Пример 4.2. Решить систему методом релаксации, производя вычисления с двумя десятичными знаками.
(4.14)
Решение. Приведем систему (4.14) к виду, удобному для релаксации:
(4.15)
В качестве начального приближения выбираем .
Находим соответствующие невязки: , , . Выбираем максимальную невязку и полагаем , тогда:
Опять выбираем максимальную невязку и полагаем , тогда:
Далее
,
,
,
,
,
Окончательно получим:
Размещено на Allbest.ru
...Подобные документы
Сущность итерационного метода решения задачи, оценка его главных преимуществ и недостатков. Разновидности итерационных методов решения систем линейных алгебраических уравнений: Якоби, Хорецкого и верхней релаксации, их отличия и возможности применения.
курсовая работа [39,2 K], добавлен 01.12.2009Решение системы линейных алгебраических уравнений большой размерности с разреженными матрицами методом простого итерационного процесса. Понятие нормы матрицы и вектора. Критерии прекращения итерационного процесса. Выбор эффективного итерационного метода.
лабораторная работа [21,8 K], добавлен 06.07.2009Характеристика и использование итерационных методов для решения систем алгебраических уравнений, способы формирования уравнений. Методы последовательных приближений, Гаусса-Зейделя, обращения и триангуляции матрицы, Халецкого, квадратного корня.
реферат [60,6 K], добавлен 15.08.2009Метод последовательного исключения неизвестных (метод Гаусса) при решении задач аппроксимации функции в прикладной математике. Метод Гаусса с выбором главного элемента и оценка погрешности при решении системы линейных уравнений, итерационные методы.
контрольная работа [94,4 K], добавлен 04.09.2010Решение нелинейных уравнений. Отделения корней уравнения графически. Метод хорд и Ньютона. Система линейных уравнений, прямые и итерационные методы решения. Нормы векторов и матриц. Метод простых итераций, его модификация. Понятие про критерий Сильвестра.
курсовая работа [911,6 K], добавлен 15.08.2012Исследование метода квадратных корней для симметричной матрицы как одного из методов решения систем линейных алгебраических уравнений. Анализ различных параметров матрицы и их влияния на точность решения: мерность, обусловленность и разряженность.
курсовая работа [59,8 K], добавлен 27.03.2011Решение задач систем линейных алгебраических уравнений, матричных уравнений, методы Гаусса и Кремера. Нахождение длины и координат вектора и исчисление его скалярного произведения. Уравнение прямой и определение координат точек неравенства; пределы.
контрольная работа [220,9 K], добавлен 06.01.2011Метод Зейделя как модификация метода простой итерации. Особенности решения систем линейных алгебраических уравнений. Анализ способов построения графика функций. Основное назначение формул Симпсона. Характеристика модифицированного метода Эйлера.
контрольная работа [191,3 K], добавлен 30.01.2014Методы решения систем линейных алгебраических уравнений (СЛАУ): Гаусса и Холецкого, их применение к конкретной задаче. Код программы решения перечисленных методов на языке программирования Borland C++ Builder 6. Понятие точного метода решения СЛАУ.
реферат [58,5 K], добавлен 24.11.2009Итерационные методы (методы последовательных приближений) для решения уравнений. Одношаговые итерационные формулы. Метод последовательных приближений Пикара. Возникновение хаоса в детерминированных системах. Методы решения систем алгебраических уравнений.
контрольная работа [166,2 K], добавлен 04.09.2010Изучение способов решения нелинейных уравнений: метод деления отрезка пополам, комбинированный метод хорд и касательных. Примеры решения систем линейных алгебраических уравнений. Особенности математической обработки результатов опыта, полином Лагранжа.
курсовая работа [181,1 K], добавлен 13.04.2010Методы решения систем линейных уравнений. Метод Якоби в матричной записи. Достоинство итерационного метода верхних релаксаций, вычислительные погрешности. Метод блочной релаксации. Разбор метода релаксаций в системах линейных уравнений на примере.
курсовая работа [209,1 K], добавлен 27.04.2011Изучение основ линейных алгебраических уравнений. Нахождение решения систем данных уравнений методом Гаусса с выбором ведущего элемента в строке, в столбце и в матрице. Выведение исходной матрицы. Основные правила применения метода факторизации.
лабораторная работа [489,3 K], добавлен 28.10.2014Способы решения системы уравнений с двумя переменными. Прямая как график линейного уравнения. Использование способов подстановки и сложения при решении систем линейных уравнений с двумя переменными. Решение системы линейных уравнений методом Гаусса.
реферат [532,7 K], добавлен 10.11.2009Понятие и специфические черты системы линейных алгебраических уравнений. Механизм и этапы решения системы линейных алгебраических уравнений. Сущность метода исключения Гаусса, примеры решения СЛАУ данным методом. Преимущества и недостатки метода Гаусса.
контрольная работа [397,2 K], добавлен 13.12.2010Рассмотрение систем линейных алгебраических уравнений общего вида. Сущность теорем и их доказательство. Особенность трапецеидальной матрицы. Решение однородных и неоднородных линейных алгебраических уравнений, их отличия и применение метода Гаусса.
реферат [66,4 K], добавлен 14.08.2009Основные действия над матрицами, операция их умножения. Элементарные преобразования матрицы, матричный метод решения систем линейных уравнений. Элементарные преобразования систем, методы решения произвольных систем линейных уравнений, свойства матриц.
реферат [111,8 K], добавлен 09.06.2011Суть метода Зейделя. Расчет разностных схемам относительно неизвестной сеточной функции. Параллельное решение систем линейных алгебраических уравнений. Процедура построения параллельного алгоритма Зейделя. Оценка ускорения представленного алгоритма.
контрольная работа [98,1 K], добавлен 09.01.2011Структура и элементы, принципы формирования и правила разрешения систем линейных алгебраических уравнений. История развития различных методов решения: матричного, Крамера, с помощью функции Find. Особенности применения возможностей программы Mathcad.
контрольная работа [96,0 K], добавлен 09.03.2016Основные правила решения системы заданных уравнений методом Гаусса с минимизацией невязки и методом простых итераций. Понятие исходной матрицы; нахождение определителя для матрицы коэффициентов. Пример составления блок-схемы метода минимизации невязок.
лабораторная работа [264,1 K], добавлен 24.09.2014
