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

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

обрщаются в нуль.

Покажем, что для возможности применения метод прогонки достаточно потребовать, чтобы коэффициенты системы (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)- й стодбец. В результате на необходимом нам месте оказывается ненулевой элемент , уже преобразованная часть матрицы не меняется, можно применять обычный шаг метода Данилевского к матрице . Она подбна матрице (и, следовательно, исходной матрице А ), т.к. елементарная матрица перестановок совпадает со своей обратной, т.е.

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

где і - единичные матрицы соответствующей размерности, а квадратные матрицы и имееют вид:


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

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

Предположим теперь, что матрица А подобным преобразованиям

уже приведена к нормальной форме Фробениуса. Решая характеристическое уравнение

,

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

Теперь стоит задача отыскать собственные векторы, соответствующие этим собственным значениям, т.е. векторы такие, что

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

ТЕОРЕМА. Пусть є есть собственное значение , а есть соответствующий собственный вектор матрицы Р , которая подобна матрице А ,т.е.

Тогда есть собственный вектор матрицы А , соответствующий собственному значению

Доказательство.Тривиально следует из того, что

Домножая левую и правую часть этого равенства слева на S ,

имеем

А это и означает, что -собственный вектор матрицы А ,

отвечающий собственному значению

Найдем собственный вектор матрицы Р , которая имеет нормальную форму Фробениуса и подобна матрице А. Записывая в развернутой форме, имеем

или

В этой системе одна из переменных может быть сделана свободной и ей может быть придано произвольное значение. В качестве таковой возьмем и положим

Тогда последовательно находим

,

т.е. искомый собственный вектор матрицы Р имеет вид

.

Если процесс приведения матрицы А к форме Р был регулярным, то

В соответствии с теоремой собственным вектором матрицы А для собственного значения будет вектор

Таким образом, задача вычисления собственных векторов матрицы А решена.


НАБЛИЖЕННЯ ФУНКЦІЙ. ЗАДАЧА ІНТЕРПОЛЯЦІЇ.


Задача наближення функцій виникає при розв’язанні багатьох задач ( обробка експериментальних даних, чисельне диференціювання та інтегрування функцій, розв’язання диференціальних та інтегральних рівнянь).

Дуже зручною у використанні на практиці функцією є многочлен. Щоб задати многочлен, треба задати тільки скінченну кількість його коефіцієнтів. Значення многочлена просто обчислюються (згадаємо схему Горнера), його легко продиференціювати, проінтегрувати і т.і. Тому алгебраїчні многочлени знайшли широке застосування для наближення (апроксимації) функцій.

Розглянемо декілька задач наближення функцій.

Постановка задачі інтерполяції. Нехай відомі значення деякої функції у різних точках які позначимо

Виникає задача поновлення ( наближеного) функції у довільній точці .

Іноді відомо, що наближену функцію доцільно шукати у вигляді

де вигляд функції відомий, а параметри треба визначити.

Коли параметри визначаються з умови збігу і наближеної функції у точках тобто то такий спосіб наближення називається інтерполяцією. Точки називаються вузлами інтерполяції.

Серед способів інтерполяції найбільш поширеним є випадок лінійної інтерполяції .

де - деякі відомі функції. Значення коефіцієнтів визначаються з умови збігу з вихідною функцією у вузлах інтерполяції

(1)

тобто з системи n +1 лінійних рівнянь з n+1 невідомими

У окремому випадку, коли

(2)

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

ТЕОРЕМА. Якщо вузли интерполяції різні, то існує єдиний інтерполяційний многочлен n-го ступеню.

Доведення . Дійсно, система рівнянь (1) у цьому випадку має вигляд

(3)

Її визначник є визначником Вандермонда

(4)

У тому, що має місце права частина рівності (4) , можна переконатися наступним чином.

Віднімаючи перший рядок з усіх наступних, маємо


Віднімаючи тепер з кожного стовпця попередній, що множиться на одержуємо

де

теж є визначником Вандермонда, порядок якого на одиницю менше порядку попереднього.

Зробивши з ним те ж, що з попереднім, одержимо

Продовжуючи аналогічні викладки остаточно одержимо рівність (4).

Бачимо, що при

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

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

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

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