Реферат на тему Прямые методы решения систем линейных алгебраических уравнений
Работа добавлена на сайт bukvasha.net: 2015-01-09Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Реферат з курсу “Введение в численные методы”
Тема: “ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ”
Содержание
1. Метод последовательных приближений
2. Метод Гаусса-Зейделя
3. Метод обращения матрицы
4. Триангуляция матрицы
5. Метод Халецкого
6. Метод квадратного корня
Литература
1. Метод последовательных приближений
Наиболее распространенными методами применительно к большим системам являются итерационные методы, использующие разложение матрицы на сумму матриц, и итерационные методы, использующие факторизацию матрицы, т.е. представление в виде произведения матриц.
Простая итерация: уравнение приводится к виду , например, следующим образом:
,
где и содержат произвольную матрицу коэффициентов, по возможности желательно близкую к .
Если выбрать A=H+Q так, чтобы у положительно определенной H легко находилась , тогда исходная система приводится к следующему удобному для итераций виду:
.
В этом случае, при симметричной матрице A и положительно определенной Q итерационный процесс сходится при любом начальном .
Если взять H в виде диагональной матрицы D= , в которой лишь на главной диагонали расположены ненулевые компоненты, то этот частный случай называется итерационным методом Якоби.
2. Метод Гаусса-Зейделя
Метод Гаусса-Зейделя отличается тем, что исходная матрица представляется суммой трех матриц:
.
Подстановка в и несложные эквивалентные преобразования приводят к следующей итерационной процедуре:
.
Различают две модификации: одновременную подстановку и последовательную. В первой модификации очередная подстановка выполняется тогда, когда будут вычислены все компоненты нового вектора. Во второй модификации очередная подстановка вектора выполняется в тот момент, когда будет вычислена очередная компонента текущего вектора. В векторно-матричной форме записи последовательная подстановка метода Гаусса-Зейделя выглядит так:
.
Вторая форма требует существенно меньшее число итераций.
3. Метод обращения матрицы
Эквивалентные преобразования матрицы в произведение более простых, приводящих к решению или облегчающих его получение, начнем с рассмотрения метода обращения матрицы. Так как в общем виде решение системы представляется через обратную матрицу в виде , то предположим, что
,
тогда, умножив справа равенство на матрицу A , получим
.
Отсюда можно сделать вывод, что матрицы должны последовательно сводить матрицу A к единичной. Если преобразующую матрицу выбрать так, чтобы только один ее столбец отличался от единичных векторов-столбцов, т.е. , то вектор-столбец можно сформировать таким, чтобы при умножении на текущую преобразуемую матрицу в последней i-тый столбец превратился в единичный . Для этого берут
и тогда .
Фактически это матричное произведение преобразует все компоненты промежуточной матрицы по формулам, применяемым в методе исключения Гаусса. Особенность этого процесса заключается в том, что диагональные элементы исходной и всех промежуточных матриц не должны быть нулевыми.
Кроме обратной матрицы, равной произведению всех T-матриц, теперь можно получать и решения уравнений для любого вектора в правой части.
4. Триангуляция матрицы
Разложение исходной матрицы на произведение двух треугольных матриц (триангуляция матрицы) не является однозначной. В соответствии с этим имеется несколько различных методов, привлекательных с той или иной стороны.
Сам способ формирования уравнений или формул для вычисления элементов треугольных матриц в различных методах практически одинаков: это метод неопределенных коэффициентов.
Различия возникают на стадии выбора условий разрешения полученных уравнений. Пусть
,
где –
нижняя треугольная матрица,
–
верхняя треугольная матрица.
Выполняя перемножения треугольных матриц и приравнивая получающиеся элементы соответствующим элементам исходной матрицы несложно для k-той строки и m-того столбца записать
.
Полученная система состоит из уравнений и содержит неизвестных коэффициентов. За счет лишних n неизвестных существует свобода выбора, благодаря которой и имеется разнообразие методов разложения.
5. Метод Халецкого
Если положить , то разложение и последующее решение системы из двух векторно-матричных уравнений с треугольными матрицами называется методом Халецкого.
Элементы треугольных матриц L и U последовательно будут вычисляться по следующим формулам:
Если исходная матрица симметричная, то от треугольных матриц можно потребовать, чтобы они были друг к другу транспонированными, т.е., например, и так, что . В этом случае элементы треугольных матриц находятся в соотношении и, следовательно, число неизвестных уменьшается вдвое. В результате элементы треугольной матрицы могут вычисляться по следующим формулам:
6. Метод квадратного корня
Использование разложения на взаимно транспонированные треугольные матрицы при решении систем алгебраических уравнений называется метод квадратного корня.
Метод разложения на транспонированные треугольные матрицы имеет модификацию, заключающуюся в выделении в произведении диагональной матрицы D с элементами на диагонали . Таким образом, для исходной матрицы, которая может быть и эрмитовой (симметричной и комплексно сопряженной), разыскивается произведение трех матриц: .
Каждое km-тое уравнение, определяется произведением k-того вектора-строки левой треугольной матрицы на диагональную матрицу, умноженную на m-тый столбец правой треугольной матрицы, и имеет вид:
.
Для однозначного разложения, учитывая комплексную сопряженность симметричных элементов треугольных матриц, в первом уравнении (i=1), имеющем вид , полагают . В этом случае
.
Аналогично, отделяя знак диагонального элемента диагональной матрицы от его модуля, можно получить формулы для вычисления :
Литература
1. Хеннер Е. К., Лапчик М. П., Рагулина М. И. Численные методы. Изд-во: "Академия/Academia", 2004. – 384c.
2. Бахвалов И. В. Численные методы. БИНОМ, 2008. – 636c.
3. Формалев В. Д., Ревизников Д. Л. Численные методы. Изд-во: ФИЗМАТЛИТ®, 2004. – 400c.
Тема: “ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ”
Содержание
1. Метод последовательных приближений
2. Метод Гаусса-Зейделя
3. Метод обращения матрицы
4. Триангуляция матрицы
5. Метод Халецкого
6. Метод квадратного корня
Литература
1. Метод последовательных приближений
Наиболее распространенными методами применительно к большим системам являются итерационные методы, использующие разложение матрицы на сумму матриц, и итерационные методы, использующие факторизацию матрицы, т.е. представление в виде произведения матриц.
Простая итерация: уравнение
где
Если выбрать A=H+Q так, чтобы у положительно определенной H легко находилась
В этом случае, при симметричной матрице A и положительно определенной Q итерационный процесс сходится при любом начальном
Если взять H в виде диагональной матрицы D=
2. Метод Гаусса-Зейделя
Метод Гаусса-Зейделя отличается тем, что исходная матрица представляется суммой трех матриц:
Подстановка в
Различают две модификации: одновременную подстановку и последовательную. В первой модификации очередная подстановка выполняется тогда, когда будут вычислены все компоненты нового вектора. Во второй модификации очередная подстановка вектора выполняется в тот момент, когда будет вычислена очередная компонента текущего вектора. В векторно-матричной форме записи последовательная подстановка метода Гаусса-Зейделя выглядит так:
Вторая форма требует существенно меньшее число итераций.
3. Метод обращения матрицы
Эквивалентные преобразования матрицы в произведение более простых, приводящих к решению или облегчающих его получение, начнем с рассмотрения метода обращения матрицы. Так как в общем виде решение системы представляется через обратную матрицу в виде
тогда, умножив справа равенство на матрицу A , получим
Отсюда можно сделать вывод, что матрицы
Фактически это матричное произведение преобразует все компоненты промежуточной матрицы по формулам, применяемым в методе исключения Гаусса. Особенность этого процесса заключается в том, что диагональные элементы исходной и всех промежуточных матриц не должны быть нулевыми.
Кроме обратной матрицы, равной произведению всех T-матриц, теперь можно получать и решения уравнений для любого вектора в правой части.
4. Триангуляция матрицы
Разложение исходной матрицы на произведение двух треугольных матриц (триангуляция матрицы) не является однозначной. В соответствии с этим имеется несколько различных методов, привлекательных с той или иной стороны.
Сам способ формирования уравнений или формул для вычисления элементов треугольных матриц в различных методах практически одинаков: это метод неопределенных коэффициентов.
Различия возникают на стадии выбора условий разрешения полученных уравнений. Пусть
где
нижняя треугольная матрица,
верхняя треугольная матрица.
Выполняя перемножения треугольных матриц и приравнивая получающиеся элементы соответствующим элементам исходной матрицы несложно для k-той строки и m-того столбца записать
Полученная система состоит из
5. Метод Халецкого
Если положить
Элементы треугольных матриц L и U последовательно будут вычисляться по следующим формулам:
Если исходная матрица симметричная, то от треугольных матриц можно потребовать, чтобы они были друг к другу транспонированными, т.е., например,
6. Метод квадратного корня
Использование разложения на взаимно транспонированные треугольные матрицы при решении систем алгебраических уравнений называется метод квадратного корня.
Метод разложения на транспонированные треугольные матрицы имеет модификацию, заключающуюся в выделении в произведении диагональной матрицы D с элементами на диагонали
Каждое km-тое уравнение, определяется произведением k-того вектора-строки левой треугольной матрицы на диагональную матрицу, умноженную на m-тый столбец правой треугольной матрицы, и имеет вид:
Для однозначного разложения, учитывая комплексную сопряженность симметричных элементов треугольных матриц, в первом уравнении (i=1), имеющем вид
Аналогично, отделяя знак диагонального элемента диагональной матрицы от его модуля, можно получить формулы для вычисления
Литература
1. Хеннер Е. К., Лапчик М. П., Рагулина М. И. Численные методы. Изд-во: "Академия/Academia", 2004. – 384c.
2. Бахвалов И. В. Численные методы. БИНОМ, 2008. – 636c.
3. Формалев В. Д., Ревизников Д. Л. Численные методы. Изд-во: ФИЗМАТЛИТ®, 2004. – 400c.