рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Алгебраических уравнений

Алгебраических уравнений - раздел Математика, Численные методы алгебры Рассмотрим Задачу Решения Системы Уравнений Вида: (11) ( )...

Рассмотрим задачу решения системы уравнений вида:

(11)

( )

или , где - матрица коэффициентов системы, - вектор неизвестных, - вектор правых частей.

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

Известно, что решение системы линейных уравнений можно выразить по формулам Крамера через отношение определителей. Но вычисление определителя не проще, чем решение исходной системы. Для решения системы порядка n необходимо вычислить (n+1) определитель, т. е. вычисление решения по формулам Крамера в (n+1) раз более трудоемко, чем решение системы другим методом, например методом Гаусса.

Метод Гаусса основан на приведении путем эквивалентных преобразований исходной системы (11) к виду с верхней треугольной матрицей.

(12)

Тогда из последнего уравнения сразу определяем

.

Подставляя его в предпоследнее уравнение, находим

 

и т. д.

Общие формулы имеют вид

, k=n, n-1,..., 1. (13)

При вычислениях по формулам (13) потребуется выполнить примерно 1/2n2 арифметических действий.

Приведение системы (11) к виду (12) можно выполнить, последовательно заменяя строки матрицы системы их линейными комбинациями.

Первое уравнение не меняется. Вычтем из второго уравнения системы (11) первое, умноженное на такое число, чтобы обратился в нуль коэффициент при . Затем таким же образом вычтем первое уравнение из третьего, четвертого и т. д. Тогда исключатся все коэффициенты первого столбца, лежащие ниже главной диагонали.

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

Запишем общие формулы процесса. Пусть проведено исключение коэффициентов из k-1 столбца. Тогда остались такие уравнения с ненулевыми элементами ниже главной диагонали:

(14)

Умножим k-ю строку на число

(15)

и вычтем из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

 

(16)

 

Производя вычисления по этим формулам при всех указанных индексах, исключим элементы k-го столбца. Будем называть такое исключение циклом процесса. Выполнение всех циклов называется прямым ходом исключения.

Запишем треугольную систему, получающуюся после выполнения всех циклов. При приведении системы к треугольному виду освободятся клетки в нижней половине матрицы системы (11). Получим

(17)

Треугольная система (17) легко решается обратным ходом по формулам (13).

Исключение по формулам (15) нельзя проводить, если в ходе расчета на главной диагонали оказался нулевой элемент Но в первом столбце промежуточной системы (14) все элементы не могут быть нулями: это означало бы, что det A = 0. Перестановкой строк можно переместить ненулевой элемент на главную диагональ и продолжить расчет.

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

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

Для прямого хода метода Гаусса число арифметических операций, в соответствии с формулами (15), (16), равно

 

Для обратного хода по формулам (13) число арифметических операций равно

 

 

Общие вычислительные затраты метода Гаусса:

 

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

Выполнение прямого хода метода Гаусса позволяет также вычислить значение определителя матрицы системы.

При замене строк матрицы их линейными комбинациями значение определителя не меняется. Знак меняется при каждой перестановке строк. Для треугольной матрицы величина определителя равна произведению элементов, стоящих на главной диагонали. Поэтому определитель вычисляется по формуле:

 

Метод Гаусса может быть использован для нахождения обратной матрицы. Обозначим ее элементы через . Тогда соотношение можно записать так:

 

Видно, что если рассматривать j-й столбец обратной матрицы как вектор, то он является решением линейной системы вида (11) с матрицей и специальной правой частью (в которой на месте стоит единица, а на остальных нули).

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

Преобразование матрицы требует порядка операций. Действия по преобразованию правых частей систем и обратный ход метода Гаусса повторяются раз, а однократное преобразование правых частей и обратный ход требуют порядка операций. Следовательно, суммарные вычислительные затраты на обращение матрицы составляют: .

Таким образом, преобразование матрицы требуется порядка 2/3n3 операций. Для преобразования правых частей и для обратного хода требуется порядка 3/2n2 операций. Всего таких преобразований n, получаем суммарные затраты

2/3n3 + 3/2n2n = 13/6n3.

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

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

[О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах]

[Home|Кафедра|ПетрГУ]2.3. Итерационные методы. Общая схема

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

При этом вектор выражается через известные предыдущие вектора Если при вычислении используется только вектор , то итерационный метод называется одношаговым (или двухслойным) методом.

Общий вид линейного одношагового метода

(18)

Важную роль играет запись итерационных методов в единой (канонической) форме.

Она имеет вид:

, (19)

где A - матрица исходной системы уравнений (1),

- некоторая последовательность невырожденных матриц,

- итерационные параметры,

Связь между записью итерационного метода в виде (18) и в виде (19) выражается формулами:

 

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

Если - единичная матрица, то метод называют явным: находится по явной формуле

(20)

В общем случае, при , метод называют неявным итерационным методом: для определения надо решать систему уравнений

(21)

Естественно требовать, чтобы объем вычислений для решения системы (21) был меньше, чем объем вычислений для исходной системы (1).

Точность метода характеризуется величиной погрешности , т.е. разностью между решением уравнения (19) и точным решением исходной системы линейных алгебраических уравнений. Подстановка в (19) приводит к системе уравнений для погрешности:

(22)

Говорят, что итерационный метод сходится, если при .

В случае, когда и ( и - соответственно) не зависят от номера итерации k, итерационный метод называется стационарным (иначе - нестационарным).

Критерий сходимости стационарного линейного одношагового итерационного метода

(23)

формулируется в теореме 1.

Теореме 1. Метод (23) сходится для любого начального приближения тогда и только тогда, когда все собственные числа матрицы перехода S по модулю меньше единицы.

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

Необходимость. Пусть некоторое собственное число матрицы перехода по модулю больше единицы. Возьмем в качестве начального приближения вектор , где s - собственный вектор, соответствующий собственному числу .

Тогда ,

 

при .

Если , то при .

Достаточность. Пусть матрица S имеет n линейно независимых собственных векторов (т.е. является матрицей простой структуры): , соответствующих собственным числам , каждое из которых по модулю меньше единицы. Разложим погрешность начального приближения по базису из собственных векторов.

 

Тогда

 

 

где (спектральный радиус). Так как , то при , т.е. метод сходится.

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

В качестве следствия из теоремы 1 можно получить легко проверяемые на практике достаточные условия. Норма матрицы S, согласованная с векторной нормой удовлетворяет неравенству для любого вектора x. Так как для максимального по модулю собственного числа матрицы S и соответствующего собственного вектора y выполняется равенство , то для любой согласованной нормы матрицы .

Примерами легко вычисляемых согласованных норм являются:

, .

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

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

Теорема 2. Пусть A - симметричная положительная матрица и выполнено условие

(24)

Тогда метод итераций

(25)

сходится.

Напомним, что матрица положительная, если для любого ненулевого вектора x (Ax,x)>0.

Неравенство (24) означает, что для любого ненулевого вектора x матрица положительна.

не стремится к нулю при .

[О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах]

[Home|Кафедра|ПетрГУ]


 

– Конец работы –

Эта тема принадлежит разделу:

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

Введение... Развитие численных методов решения задач Понятие вычислительного... Численные методы алгебры...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгебраических уравнений

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Одношаговые и многошаговые разностные схемы для задачи Коши для ОДУ 1-го порядка. Разностные схемы для краевых задач для ОДУ 2-го порядка.
[О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах] [Home|Кафедра|ПетрГУ] Роль численныхметодов Понятие точного и приближенногорешения математическо

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

Оценкапогрешности и мера обусловленности
Оценка погрешности решения системы через погрешности исходных данный мера обусловленности матрицы. Алгебраическаяпроблема собственных значений По

Квадратурныеформулы
Постановка задачи численногоинтегрирования Формулы прямоугольников Построение и оценка погрешности Формулы левых, правыхи средних прямоугольников Обобщенная формула п

Краевыезадачи для ОДУ
Граничныеусловия Методстрельбы для краевой задачи с ОДУ второго порядка Разностныесхемы для краевой задачи с ОДУ 2-го порядка Простейшаязадача

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

Погрешности данных, метода и вычислений
Почти всегда используемые на практике решения математических задач имеют некоторые погрешности. Погрешность решения задачи обуславливается следующими причинами: 1. Математическое

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

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

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

Метод деления отрезка пополам
Одним из итерационных методов является метод деления отрезка пополам (дихотомии, бисекции). На первом этапе должен быть найден отрезка такой, что < 0. Тогда отрезок содержит не

Метод хорд
В некоторых случаях несколько большей скоростью сходимости обладает метод хорд, у которого на втором этапе при выборе очередного приближения внутри отрезка, содержащего корень, учитывается величина

Метод Ньютона
Геометрический смысл метода Ньютона (метода касательных) заключается в том, что на отрезке содержащем корень уравнения (1) график функции заменяется отрезком касательной, проведенной к графику при

Метод простых итераций
В качестве первого примера рассмотрим явный стационарный итерационный метод, каноническая форма которого: (26) Выясним достаточные условия сходимости этого метода. В соответствии

Метод Якоби
Координатная форма записи этого варианта итерационного метода имеет вид: . ( 27) Формулы (27) получаются непосредственно из исходной системы, если i - ое уравнение системы

Метод Зейделя
Весьма широко на практике применяется итерационный метод Зейделя:   Компоненты находятся последовательно по формулам:   Запишем этот метод в матричной

Оценка погрешности и мера обусловленности
Предположим, что матрица системы линейных уравнений и вектор правых частей заданы неточно и вместо предъявленной к решению системы (30) в действительности решается некоторая систе

Метод простых итераций
В качестве первого примера рассмотрим явный стационарный итерационный метод, каноническая форма которого: (26) Выясним достаточные условия сходимости этого метода. В соответствии

Метод Якоби
Координатная форма записи этого варианта итерационного метода имеет вид: . ( 27) Формулы (27) получаются непосредственно из исходной системы, если i - ое уравнение системы

Метод Зейделя
Весьма широко на практике применяется итерационный метод Зейделя:   Компоненты находятся последовательно по формулам:   Запишем этот метод в матричной

Оценка погрешности и мера обусловленности
Предположим, что матрица системы линейных уравнений и вектор правых частей заданы неточно и вместо предъявленной к решению системы (30) в действительности решается некоторая систе

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

Метод вращений
Метод вращения позволяет для симметрических матриц решать полную проблему собственных значений. Сущность метода состоит в следующем. Известно, что для симметрической матрицы A

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

Постановка задачи
Пусть задана функция . Часто нахождение значений этой функции может оказаться трудоемкой задачей. Например, - параметр в некоторой сложной задаче, после решения которой определяется значение f(x),

Построение интерполяционного многочлена Лагранжа
Наиболее простой и (для многих случаев) удобной является система функций , . Функция при этом представляет собой многочлен степени (интерполяционный многочлен) с коэффициентами . Система у

Остаточный член
В узлах многочлен Лагранжа совпадает с заданной функцией, в остальных точках в общем случае не совпадает с (кроме случая, когда многочлен степени не выше ). Разность - - остаточный член. Запишем ее

Постановка задачи
- остаточный член формулы Лагранжа. Для получено выражение : (7) Оно получено в предположении, что производная существует и ограничена. Для одной определенной функции точ

Многочлены Чебышева
Пусть . Рассмотрим функцию вида: (9) При : При : , При используем тригонометрическое тождество   Пусть многочлен степени . Получим рекурен

Минимизация оценки остаточного члена
Пусть приближена на отрезке интерполяционным многочленом степени . Оценка остаточного члена: . Величина на отрезке [-1,1] будет минимальна, если окажется многочленом . совпадает с

Оценка погрешности по методу Рунге..
Погрешность приближенного решения во многих задачах, когда одним из определяющих параметров алгоритма является положительная величина - шаг сетки, можно записать в виде: (

Уточнение приближенного решения.
Выражение (30) можно использовать для уточнения приближенной величины , т.к. добавление к ней дает новое приближение , погрешность которого. (32) Формула (32) наз

Линейный интерполяционный сплайн
Пусть - разбиение отрезка . , - заданные значения. Сплайном первой степени называется :непрерывная на отрезке , линейная на каждом частичном промежутке функция. Его обозначение .

Сходимость.
Пусть на задана последовательность сеток : , , которая удовлетворяют условию при . Для строится интерполяционный сплайн . Интерполяционный процесс сходится, если при для любой функции из некот

Кубический интерполяционный сплайн
Пусть на задана сетка , в узлах которой известны значения функции . Сплайн третьей степени , интерполирующий заданную функцию , определяется как функция, удовлетворяющая условиям:

Пусть требуется найти решение следующей системы линейных алгебраических уравнений
(45) причем для всех . Матрица этой системы является трехдиагональной и имеет следующий вид:   Это квадратная матрица размера . Предположим, что им

Среднеквадратичные приближения.
Однозначной задача определения параметров станет, если рассматривать как показатель качества аппроксимации величину (54) и искать , минимизирующие функцию . Решение задачи о нахожд

Оценка погрешности.
Пусть существует , непрерывная на . По формуле Тейлора: . Интегрируя, получаем: (60) Обозначим . Используем вариант теоремы о среднем, который имеет вид

Обозначим . Тогда
, . Дифференцируя по , получаем: , .   Теперь интегрируя по , находим:   Используя теорему о среднем получаем: , где . Еще р

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

Рассмотрим вопрос об устойчивости задачи Коши
, по начальным данным. Пусть - решение задачи Коши с начальным условием . Тогда для функции можно написать дифференциальное уравнение , , где , .

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

Рассмотрим вопрос о сходимости схем семейства (9) в применении к модельной задаче Коши
, , . Разностная схема (9) принимает вид , отсюда можно заключить, что , где , . Выведем теперь рекуррентную формулу для погр

Сценарий построения разностных схем
В разделе 3.2.1. был приведен общий вид разностной схемы для многошаговых методов. В частности, для решения задачи Коши , . наиболее употребительными являются -шаговые методы вида

Построение двухшаговой и трехшаговой схем
Для составления квадратурной формулы применим интерполяционную формулу Ньютона с разделенными разностями (см. раздел 3.3). Введем функцию , определенную следующим образом: . Тогда

Устойчивость на модельной задаче
Исследуем устойчивость разностной схемы (15) на модельной задаче , , . Для модельного уравнения схема примет вид   или Ошибка! Закладка не

Построение неявных схем
Для построения -шаговой неявной (интерполяционной) схемы будем использовать интерполяционный многочлен Ньютона, построенный по значениям функции в узлах : , где ,

Нахождение решения неявной разностной схемы
Двухточечная неявная схема Адамса (19) имеет вид нелинейного уравнения относительно неизвестного значения: , (20) где , . Для решения уравнения

Граничные условия
Кроме задачи Коши, в которой дополнительные условия, накладываемые на решение ОДУ и его производные, задаются в одной точке , существует большое число задач с дифференциальными уравнениями, в котор

Метод стрельбы для краевой задачи с ОДУ 2-го порядка
Рассмотрим краевую задачу (22) (23) Рассмотрим также задачу Коши для уравнения (22) с начальными условиями , (24) где - угол наклона касательной к интег

Построение трехточечной разностной схемы 2-го порядка аппроксимации.
Рассмотрим линейное дифференциальное уравнение второго порядка в самосопряженной форме (28) на интервале с краевыми условиями первого рода: (29) Если , , то така

Сходимость разностной схемы.
Для исследования сходимости рассмотрим погрешность разностной схемы в узлах сетки:   Пользуясь линейностью оператора (33) и введенными ранее безиндексными об

Краевые условия 2-го и 3-го рода.
Рассмотрим теперь уравнение (28) с краевыми условиями 2-го или 3-го рода (30):   Будем решать эту задачу с помощью трехточечной разностной схемы (31) с условиями на коэффицие

Построение трехточечной разностной схемы 2-го порядка аппроксимации.
Рассмотрим линейное дифференциальное уравнение второго порядка в самосопряженной форме (28) на интервале с краевыми условиями первого рода: (29) Если , , то така

Сходимость разностной схемы.
Для исследования сходимости рассмотрим погрешность разностной схемы в узлах сетки:   Пользуясь линейностью оператора (33) и введенными ранее безиндексными об

Краевые условия 2-го и 3-го рода.
Рассмотрим теперь уравнение (28) с краевыми условиями 2-го или 3-го рода (30):   Будем решать эту задачу с помощью трехточечной разностной схемы (31) с условиями на коэффицие

Формула Симпсона
          [О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах] Численное решение задачи Коши для обыкновенных дифф

В соответствии с этим методом приближенное решение задачи Коши ищется с помощью неявной разностной схемы
  где . Значение определяется с помощью метода Рунге-Кутты. Для решения неявного нелинейного уравнения предлагается воспользоваться методом последовательных приближений: .

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги