Xreferat.com » Рефераты по математике » Численные методы

Численные методы

общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид

Численные методы

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

Т.е. матрицу А можно записать

Численные методы

Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде

Численные методы

где Численные методы-неизвестные коэффициенты, которые последовательно находятся от Численные методы до Численные методы (прямая прогонка ), а затем последовательно вычисляются Численные методы (обратная прогонка) .

Выведем формулы для вычисления Численные методы Из (3) можно получить

Численные методы

Подставляя имеющиеся выражения для Численные методы в уравнение (1),приходим при Численные методы к уравнению Численные методы Последнее уравнение будет выполнено если коэффициенты Численные методы выбрать такими, чтобы выражения в квадратных скобках обращались в нуль.

А именно, достаточно положить Численные методыДля отыскания всех Численные методы достаточно задать Численные методы

Эти начальные значения находим из требования эквивалентности условия (3) при Численные методы т.е. условия Численные методы , первому из уравнений (2).

Таким образом, получаем

Численные методы (5)

Нахождение коэффициентов Численные методы по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты Численные методы найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с Численные методы Для начала счета по этой формуле требуется знать Численные методы , которое определяется из уравнений

Численные методы

И равно

Численные методы.

Нахождение Численные методы по формулам

Численные методы (6)

называется обратной прогонкой. Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки.

Метод прогонки можно пременять, если знаменатели выражений (4), (6) не обрщаются в нуль.

Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (1), (2) удовлетворяли условиям

Численные методы (8)

Сначала докажем по индукции, что при условиях (7), (8) модули прогоночных коэффициентов Численные методы не превосходят единицы. Согласно (5), (8) имеем Численные методы. Предположим,что Численные методы для некоторогоЧисленные методы и докажем, что Численные методы

Прежде всего для любых двух комплексных чисел Численные методы и Численные методы докажем неравенство

Численные методы

Из неравенства треугольника имеем

Численные методы

Откуда

Численные методы

Вернемся теперь к доказательству Численные методы, если Численные методы. Согласно имеем оценку

Численные методы

а, используя (7) , получаем

Численные методыЧисленные методыЧисленные методы

т.е. знаменатели выражений (4) не обращаются в нуль.

Более того

Численные методы

Следовательно, Численные методы

Далее, учитывая второе из условий (8) и только что доказанное неравенство Численные методы, имеем

Численные методы

т.е. не обращается в нуль и знаменатель в выражении для Численные методы.

К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями

Численные методы Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки.

Кроме того, доказанные неравенства Численные методы, Численные методы обеспечивают устойчивость счета по рекуррентным формулам (6). Последнее означает, что погрешность,внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам.

Действительно, пусть в формуле (6) при Численные методы вместо Численные методы вычислена величина Численные методы

Тогда на следующем шаге вычислений, т.е. при Численные методы

вместо

Численные методы получим величину Численные методы и погрешность окажется равной

Численные методы

Отсюда получаем, что Численные методы,т.е. погрешность не возрастает.

Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки.

По формулам (4), что реализуемые с помощью шести арифметических действий, вычисления производятся Численные методы раз, по формуле (6) выполняется 5 арифметических действий, наконец по формуле (3), требующей всего два действия, вычисления осуществляются Численные методыраз. Итак в методе прогонки всего затрачивается

Численные методы

арифметических действий, т.е. число действий растет линейно относительно числа неизвестных Численные методы

При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных.

ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ И СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦ.

Большое число задач математики и физики требует отыскания собственных значений и собственных векторов матриц, т.е. отыскания таких значений +Численные методы, для которых существуют нетривиальные решения однородной системы линейных алгебраических уравнений

Численные методы , (1)

и отыскания этих нетривиальных решений.

Здесь Численные методы -квадратная матрица порядка m , Численные методы- неизвестный вектор - столбец.

Из курса алгебры известно, что нетривиальное решение системы (1) существует тогда и только тогда, когда

Численные методы, (2)

где Е - единичная матрица. Если раскрыть определитель Численные методы , ïîëó÷àåòñÿ алгебраическое уравнение степени m относительно Численные методы.Таким образом задача отыскания собственных значений сводится к проблеме раскрытия определителя Численные методы по степеням Численные методы и последующему решению алгебраического уравнения m- й степени.

Определитель Численные методы называется характеристическим (или вековым ) определителем, а уравнение (2) называется характеристическим (или вековым ) уравнением.

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

Метод Данилевского развертывание векового определителя.

Определение. Квадратная матрица Р порядка m называется подобной матрице А , если она представлена в виде

Численные методы,

где S - невыродженная квадратная матрица порядка m.

ТЕОРЕМА. Характеристический определитель исходной и подобной матрицы совпадают .

Доказательство.

Численные методы

Идея метода Данилевского состоит в том, что матрица А подобным преобразованиям приводится, к так называемой нормальной форме Фробениуса

Численные методы .

Характеристическое уравнение для матрицы Р имеет простой вид

Численные методыт.е. коэффициенты при степенях Численные методы характеристического полинома непосредственно выражаются через элементы первой строки матрицы Р.

Приведение матрицы А к нормальной форме Фробениуса Р осуществляется последовательно построкам, начиная с последеней строки.

Приведем матрицу А

Численные методы

подобным преобразование к виду

Численные методы

Пусть Численные методы Можн проверить,что такой вид имеет матрица Численные методы, которая равна

Численные методы

где

Численные методы

Численные методы

Слудующий шаг - приведение матрицы Численные методы подобным преобразованием к виду Численные методы, где и вторая снизу строка имеет единицу в Численные методы-ом столбце, а все остальные элементы строки равны нулю:

Численные методы

Если Численные методыто можно проверить, что такой вид имеет матрица Численные методы:
Численные методы

гдеЧисленные методы

Численные методы

Таким образом

Численные методы

Далее процедура аналогичная, если на кождом шаге в очередной строке, на месте которого подобным преобразованием нужно получить единицу, не равную нулю.

В этом случае ( будем называт его регулярным ) нормальная формула Фробениуса будет получена за ( m-1 ) шагов и будет иметь вид

Численные методы

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

Численные методыи элемент Численные методы . Таким образом обычная процедура метода Данилевского не подходит из-за необходимости деления на ноль.

В этой ситуации возможно два случая. В первом случае к-й

строке левее элемента Численные методы есть элемент Численные методы

Численные методы Тогда домножая матрицу Численные методы слева и справа на элементарную матрицу перестановок Численные методы, получаем матрицу

Численные методы,

у которой по сравнению с матрицей Численные методы переставлены l -я и (k-1 )-я строка l-й и ( k-1)- й стодбец. В результате на необходимом нам месте оказывается ненулевой элемент Численные методы , уже преобразованная часть матрицы не меняется, можно применять обычный шаг метода Данилевского к матрице Численные методы. Она подбна матрице Численные методы (и, следовательно, исходной матрице А ), т.к. елементарная матрица перестановок совпадает со своей обратной, т.е. Численные методы

Рассмотрим второй нерегулярный

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: