Численное решение математических моделей объектов заданных системами дифференциальных уравнений
Введение:
При математическом моделировании ряда технических устройств используются системы дифференциальных нелинейных уравнений. Такие модели используются не только в технике, они находят применение в экономике, химии, биологии, медицине, управлении.
Исследование функционирования таких устройств требуют решения указанных систем уравнений. Поскольку основная часть таких уравнений являются нелинейными и нестационарными, часто невозможно получить их аналитическое решение.
Возникает необходимость использовать численные методы, наиболее известным из которых является метод Рунге — Кутты [1]. Что касается Python, то в публикациях по численным методам, например [2,3], данных по применение Рунге — Кутты крайне мало, а по его модификации — методу Рунге-Кутта-Фельберга вообще нет.
В настоящее время, благодаря простому интерфейсу, наибольшее распространение в Python имеет функцию odeint из модуля scipy.integrate. Вторая функция ode из этого модуля реализует несколько методов, в том числе и упомянутый пятиранговый метод Рунге-Кутта-Фельберга, но, вследствие универсальности, имеет ограниченное быстродействие.
Целью настоящей публикации является сравнительный анализ перечисленных средств численного решения систем дифференциальных уравнений с модифицированным автором под Python методом Рунге-Кутта-Фельберга. В публикации так же приведены решения по краевым задачам для систем дифференциальных уравнений (СДУ).
Краткие теоретические и фактические данные по рассматриваемым методам и программным средствам для численного решения СДУ
Для одного дифференциального уравнения n – го порядка, задача Коши состоит в нахождении функции, удовлетворяющей равенству:
и начальным условиям
Перед решением эта задача должна быть переписана в виде следующей СДУ
(1)
с начальными условиями
Модуль имеет две функции ode() и odeint(), предназначенные для решения систем обыкновенных дифференциальных уравнений (ОДУ) первого порядка с начальными условиями в одной точке (задача Коши). Функция ode() более универсальная, а функция odeint() (ODE integrator) имеет более простой интерфейс и хорошо решает большинство задач.
Функция odeint() имеет три обязательных аргумента и много опций. Она имеет следующий формат odeint(func, y0, t[,args=(), . ]) Аргумент func – это имя Python функции двух переменных, первой из которых является список y=[y1,y2. yn], а второй – имя независимой переменной.
Функция func должна возвращать список из n значений функций при заданном значении независимого аргумента t. Фактически функция func(y,t) реализует вычисление правых частей системы (1).
Второй аргумент y0 функции odeint() является массивом (или списком) начальных значений при t=t0.
Третий аргумент является массивом моментов времени, в которые вы хотите получить решение задачи. При этом первый элемент этого массива рассматривается как t0.
Функция odeint() возвращает массив размера len(t) x len(y0). Функция odeint() имеет много опций, управляющих ее работой. Опции rtol (относительная погрешность) и atol (абсолютная погрешность) определяют погрешность вычислений ei для каждого значения yi по формуле
Они могут быть векторами или скалярами. По умолчанию
Вторая функция модуля scipy.integrate, которая предназначена для решения дифференциальных уравнений и систем, называется ode(). Она создает объект ОДУ (тип scipy.integrate._ode.ode). Имея ссылку на такой объект, для решения дифференциальных уравнений следует использовать его методы. Аналогично функции odeint(), функция ode(func) предполагает приведение задачи к системе дифференциальных уравнений вида (1) и использовании ее функции правых частей.
Отличие только в том, что функция правых частей func(t,y) первым аргументом принимает независимую переменную, а вторым – список значений искомых функций. Например, следующая последовательность инструкций создает объект ODE, представляющий задачу Коши.
При построении численных алгоритмов будем считать, что решение этой дифференциальной задачи существует, оно единственно и обладает необходимыми свойствами гладкости.
При численном решении задачи Коши
(2)
(3)
по известному решению в точке t =0 необходимо найти из уравнения (3) решение при других t. При численном решении задачи (2),(3) будем использовать равномерную, для простоты, сетку по переменной t с шагом т > 0.
Приближенное решение задачи (2), (3) в точке обозначим . Метод сходится в точке если при . Метод имеет р-й порядок точности, если , р > 0 при . Простейшая разностная схема для приближенного решения задачи (2),(3) есть
(4)
При имеем явный метод и в этом случае разностная схема аппроксимирует уравнение (2) с первым порядком. Симметричная схема в (4) имеет второй порядок аппроксимации. Эта схема относится к классу неявных — для определения приближенного решения на новом слое необходимо решать нелинейную задачу.
Явные схемы второго и более высокого порядка аппроксимации удобно строить, ориентируясь на метод предиктор-корректор. На этапе предиктора (предсказания) используется явная схема
(5)
а на этапе корректора (уточнения) — схема
В одношаговых методах Рунге—Кутта идеи предиктора-корректора реализуются наиболее полно. Этот метод записывается в общем виде:
(6),
Формула (6) основана на s вычислениях функции f и называется s-стадийной. Если при имеем явный метод Рунге—Кутта. Если при j>1 и то определяется неявно из уравнения:
(7)
О таком методе Рунге—Кутта говорят как о диагонально-неявном. Параметры определяют вариант метода Рунге—Кутта. Используется следующее представление метода (таблица Бутчера)
Одним из наиболее распространенных является явный метод Рунге—Кутта четвертого порядка
(8)
Метод Рунге—Кутта— Фельберга
Привожу значение расчётных коэффициентов метода
(9)
С учётом(9) общее решение имеет вид:
(10)
Это решение обеспечивает пятый порядок точности, остаётся его адаптировать к Python.
Вычислительный эксперимент по определению абсолютной погрешности численного решения нелинейного дифференциального уравнения с использованием обеих функций def odein(),def oden() модуля scipy.integrate и адаптированного к Python методов Рунге—Кутта и Рунге—Кутта— Фельберга
Адаптированные к Python методы Рунге—Кутта и Рунге—Кутта— Фельберга имеют меньшую абсолютную, чем решение с применением функции odeint, но большую, чем с использованием функции edu. Необходимо провести исследование быстродействия.
Численный эксперимент по сравнению быстродействия численного решения СДУ при использовании функции ode с атрибутом dopri5 (метод Рунге – Кутты 5 порядка) и с использованием адаптированного к Python метода Рунге—Кутта— Фельберга
Сравнительный анализ проведём на примере модельной задачи, приведенной в [2]. Чтобы не повторять источник, приведу постановку и решение модельной задачи из [2].
Решим задачу Коши, описывающую движение тела, брошенного с начальной скоростью v0 под углом α к горизонту в предположении, что сопротивление воздуха пропорционально квадрату скорости. В векторной форме уравнение движения имеет вид
где – радиус вектор движущегося тела, – вектор скорости тела, – коэффициент сопротивления, вектор силы веса тела массы m, g – ускорение свободного падения.
Особенность этой задачи состоит в том, что движение заканчивается в заранее неизвестный момент времени, когда тело падает на землю. Если обозначить , то в координатной форме мы имеем систему уравнений:
К системе следует добавить начальные условия: (h начальная высота), . Положим . Тогда соответствующая система ОДУ 1 – го порядка примет вид:
Для модельной задачи положим . Опуская довольно обширное описание программы, приведу только листинг из комментариев к которому, думаю, будет ясен принцип её работы. В программу добавлен отсчёт времени работы для сравнительного анализа.
Flight time = 1.2316 Distance = 5.9829 Height =1.8542
Flight time = 1.1016 Distance = 4.3830 Height =1.5088
Flight time = 1.0197 Distance = 3.5265 Height =1.2912
Flight time = 0.9068 Distance = 2.5842 Height =1.0240
Время на модельную задачу: 0.454787
Для реализации средствами Python численного решения СДУ без использования специальных модулей, мною была предложена и исследована следующая функция:
def increment(f, t, y, tau
k1=tau*f(t,y)
k2=tau*f(t+(1/4)*tau,y+(1/4)*k1)
k3 =tau *f(t+(3/8)*tau,y+(3/32)*k1+(9/32)*k2)
k4=tau*f(t+(12/13)*tau,y+(1932/2197)*k1-(7200/2197)*k2+(7296/2197)*k3)
k5=tau*f(t+tau,y+(439/216)*k1-8*k2+(3680/513)*k3 -(845/4104)*k4)
k6=tau*f(t+(1/2)*tau,y-(8/27)*k1+2*k2-(3544/2565)*k3 +(1859/4104)*k4-(11/40)*k5)
return (16/135)*k1+(6656/12825)*k3+(28561/56430)*k4-(9/50)*k5+(2/55)*k6
Функция increment(f, t, y, tau) обеспечивает пятый порядок численного метода решения. Остальные особенности программы можно посмотреть в следующем листинге:
Время на модельную задачу: 0.259927
Предложенная программная реализация модельной задачи без использования специальных модулей имеет почти в двое большее быстродействие, чем с функцией ode, однако нельзя забывать, что ode имеет более высокую точность численного решения и возможности выбора метода решения.
Решение краевой задачи с поточно разделёнными краевыми условиями
Приведем пример некоторой конкретной краевой задачи с поточно разделенными краевыми условиями:
(11)
Для решения задачи (11) используем следующий алгоритм:
1. Решаем первые три неоднородные уравнения системы (11) с начальными условиями
Введем обозначение для решения задачи Коши:
2. Решаем первые три однородные уравнения системы (11) с начальными условиями
Введем обозначение для решения задачи Коши:
3. Решаем первые три однородные уравнения системы (11) с начальными условиями
Введем обозначение для решения задачи Коши:
4. Общее решение краевой задачи (11) при помощи решений задач Коши записывается в виде линейной комбинации решений:
где p2, p3 — некоторые неизвестные параметры.
5. Для определения параметров p2, p3, используем краевые условия последних двух уравнений (11), то есть условия при x = b. Подставляя, получим систему линейных уравнений относительно неизвестных p2, p3:
(12)
Решая (12), получим соотношения для p2, p3.
По приведенному алгоритму с применением метода Рунге—Кутта—Фельберга получим следующую программу:
y0[0]= 0.0
y1[0]= 1.0
y2[0]= 0.7156448588231397
y3[0]= 1.324566562303714
y0[N-1]= 0.9900000000000007
y1[N-1]= 0.1747719838716767
y2[N-1]= 0.8
y3[N-1]= 0.5000000000000001
Время на модельную задачу: 0.070878
Вывод
Разработанная мною программа отличается от приведенной в [3] меньшей погрешностью, что подтверждает приведенный в начале статьи сравнительный анализ функции odeint с реализованным на Python метода Рунге—Кутта—Фельберга.
3. Н.М. Полякова, Е.В. Ширяева Python 3. Создание графического интерфейса пользователя (на примере решения методом пристрелки краевой задачи для линейных обыкновенных дифференциальных уравнений). Ростов-на-Дону 2017.
Численные методы решения в алгебре и геометрии
Современная вычислительная техника требует от пользователей знаний основ вычислительной математики и применения этих знаний к решению различных задач народного хозяйства. Сложные вычислительные задачи, включающие при моделировании различных процессов и явлений можно разбить на ряд элементарных: решение уравнений, установление функциональной зависимости между результатами эксперимента, вычисление интегралов и т.д.. При решении очень многих практических задач математическая модель выражается уравнением. В школьном курсе математики мы рассматривали линейные, квадратные уравнения, уравнения третьей и четвертой степени, при решении этих уравнений получали целые, дробные и рациональные решения.
При подготовке к итоговой аттестации в одном из сборников мне встретилось уравнение х 3 +2х -7=0, которое я не смогла решить, применяя способы рассматриваемые в школьной программе. Преподователь сказал, что такое уравнение имеет приближенные корни.
А как решить уравнение, если корни его выражаются приближенными числами? На этот вопрос мне удалось найти ответ, только после изучения темы «Производная».
Скачать:
Вложение | Размер |
---|---|
исследовательская работа по алгебре и теории чисел | 362 КБ |
Предварительный просмотр:
Муниципальное образовательное учериждение
Кировская средняя общеобразовательная школа
Исследовательская работа по математике
«Численные методы решения
в алгебре и геометрии.»
Выполнила: ученица 11 класса
МОУ Кировская СОШ
Руководитель: учитель математики
МОУ Кировская СОШ
п. Средний Маныч
I. Историческая справка.
II. Численные методы решения уравнений.
1. Традиционный способ определения корней уравнения.
3. Метод косательной (метод Ньютона).
4. Комбинированный метод хорд и касательных.
5. Метод (метод последовательных приближений).
6. Метод проб (метод половинного деления).
III. Решение задач.
IV. Численные методы в геометрии.
Современная вычислительная техника требует от пользователей знаний основ вычислительной математики и применения этих знаний к решению различных задач народного хозяйства. Сложные вычислительные задачи, включающие при моделировании различных процессов и явлений можно разбить на ряд элементарных: решение уравнений, установление функциональной зависимости между результатами эксперимента, вычисление интегралов и т.д.. При решении очень многих практических задач математическая модель выражается уравнением. В школьном курсе математики мы рассматривали линейные, квадратные уравнения, уравнения третьей и четвертой степени, при решении этих уравнений получали целые, дробные и рациональные решения.
При подготовке к итоговой аттестации в одном из сборников мне встретилось уравнение х 3 +2х -7=0, которое я не смогла решить, применяя способы рассматриваемые в школьной программе. Преподователь сказал, что такое уравнение имеет приближенные корни.
А как решить уравнение, если корни его выражаются приближенными числами? На этот вопрос мне удалось найти ответ, только после изучения темы «Производная».
Цель работы: научиться находить приблизительные корни уравнений n-ной степени и трансцендентных уравнений.
При решении уравнений f(x) = 0 вначале графически находим интервал изоляции, в котором находится корень уравнения. Затем, после такого отделения корней, каждый из них может быть вычислен с любой степенью точности посредством аналитических методов. В работе рассматривается метод хорд, метод касательных (метод Ньютона), метод итераций(метод последовательных приближений) и метод проб (половиного деления).
С помощью описанных методов можно решать задачи практического содержания в различных отраслях народного хозяйства: бухгалтерии, ветеринарии, медицине, промышленности и т.д. – там, где поставленна любая математическая модель задач, сводящаяся к алгебраическим уравнениям.
I. Историческая справка.
Представьте, что в очень легком – практически невесомом – кошельке содержится какое-то количество монет одинакового достоинства. Как узнать, сколько монет в кошельке, не заглядывая внутрь? Есть очень простой способ: положить кошелек на одну чашу рычажных весов и уравновесить его монетками на другой чаше. Сколько монет для этого потребуется – столько же их и в кошельке.
Испытанный измерительный инструмент продавцов, химиков и аптекарей приходит на помощь и в чуть более сложном случае: пусть на левой чаше находящихся в равновесии весов лежат кошелек с неизвестным числом монет и еще 5 монет рядом с ним, а на правой чаше – 15 точно таких же монеток. Для того чтобы узнать, сколько монет в кошельке, снимем по 5 монет с обеих чаш – равновесие при этом не нарушится. Следовательно, внутри кошелька 10 монет.
В те далекие времена, когда мудрецы впервые стали задумываться о равенствах, содержащих неизвестные величины, наверное, еще не было ни монет, ни кошельков. Но зато были кучи, а также горшки, корзины, которые прекрасно подходили на роль тайников-хранилищ, вмещающих неизвестное количество предметов. «Ищется куча, которая вместе с двумя третями ее, половиной и одной седьмой составляет 37. », – поучал во II тысячелетии до новой эры египетский писец Ахмес. В древних математических задачах Междуречья, Индии, Китая, Греции неизвестные величины выражали число павлинов в саду, количество быков в стаде, совокупность вещей, учитываемых при разделе имущуства. Хорошо обученные науке счета писцы, чиновники и посвященные в тайные знания жрецы довольно успешно справлялись с такими задачами.
Дошедшие до нас источники свидетельствуют, что древние ученные владели какими-то общими приемами решения задач с неизвестными величинами. Однако ни в одном папирусе, ни в одной глиняной табличке не дано описание этих приемов. Авторы лишь изредка снабжали свои числовые выкладки скупыми комментариями типа: «Смотри!», «Делай так!», «Ты правильно нашел». В этом смысле исключением является «Арифметика» греческого математика Диофанта Александрийского (III в.) – собрание задач на составление уравнений с систематическим изложением их решений.
Однако первым руководством по решению задач, получившим широкую известность, стал труд багдадского ученого IX в. Мухаммеда бен Мусы аль-Хорезми. Слово «аль-джебр» из арабского названия этого тракта – «Китаб аль-джебр валь-мукабала» («Книга о восстановлении и противопоставлении») – со временем превратилось в хорошо знакомое всем слово «алгебра», а само сочинение аль-Хорезми послужило отправной точкой в становлении науки о решении уравнений.
Большой вклад в теорию о решении уравнений внес итальянский ученный Леонардо Пизанский.
Среди современников ему не было равных. И в последующие три столетия нельзя назвать ни одного ученного такого масштаба. Творчество Леонардо Пизанского (1180 – 1240) оказало решающее влияние на развитие алгебры и теории чисел, в частности на исследования таких математиков, как Франсуа Виет и Пьер Ферма.
При дворе Фридриха II устраивались научные диспуты. На одном из них придворный философ магистр Иоганн Палермский предложил Леонардо пизанскому два вопроса, которые в современных обозначениях выглядят так:
1) найти корень уравнения
х 3 + 2х 2 + 10х = 20;
2) найти рациональные решения системы уравнений
х 2 +5= и 2 ,
Леонардо провел тщательные исследования обеих хадач и написал две книги – «Цветок» и «Книга квадратов» (или «Книга о квадратных числах») 1225.), посвященные их решению. Хотя обе работы изданы типографическим способом только в 1862 г., математикам средневековой Европы они были хорошо известны.
В первой книге Леонардо установил, что корень уравнения (1) не является ни целым числом, ни дробью. Он также не может иметь вид n, n + m или n – m. Наконец, Леонардо вычислил его с точностью до шестого шестидесятеричного знака:
х = 1; 22, 7, 42, 33, 4, 40
(здесь точка с запятой отделяют целую часть от дробной, а запятые – шестидесятиричные разряды). Каким способом было полученно это значение, до сих пор остается неизвестным.
Если квадратные уравнения умели решать еще математики Вавилонии и Древней Индии, то решение урувненийпри n > 3 появились немного в конце XV века. А вот применение численных методов при нахождении корней уравнений впервые встречаются в работах Исаака Ньютона.
II. Численные методы решения алгебраических уравнений
Пусть требуется решить алгебраическое уравнение
Методы исследования поведения функции дают возможность находить приближенные значения корней уравнения (1.1).
Если данное уравнение есть алгебраическое уравнение, т.е. f ‘(х) есть многочлен, первой, второй, третьей или четвертой степени, то существуют формулы, позволяющие выразить корни уравнения через его коэффициенты с помощью конечного числа операций сложения, вычитания, умножения, деления и извлечения корней. Для уравнения выше четвертой таких формул, вообще говоря, нет.
Если коэффициенты любого уравнения, алгебраического или неалгебраического (трансцендентного), не буквенные, а числовые, то корни уравнения могут быть вычислены приближенно с любой степенью точности. Отметим, что даже в тех случаях, когда корни алгебраического уравнения выражаются через радикалы, на практике иногда целесообразно применять приближенный метод решения уравнения.
i. 1 .Графический метод, отделение корней
Задача о нахождении приближенных значений действительных корней уравнения (1.1) предусматривает предварительное отделение корня, т.е. установление промежутка, в котором других корней данного уравнения нет.
Будем предполагать, что функция f(х) в промежутке [а; b ] непрерывна со своими производными f'(х) и f «(х), значения f (а) и f (b) функции на концах промежутка имеют разные знаки, т.е. f(а) •f(b) /»(х) сохраняют знак во всем промежутке [а’,b].
Действительные корни уравнения (1.1) являются абсциссами точек пересечения кривой у =f(х) с осью Ох, а если это уравнение преобразуется к виду f 1 (х) = f 2 (х), то его действительные корни будут абсциссами точек пересечения кривых у f,(х) и у = f г (х) (см. рис.).
Реферат: Численные методы решения систем линейных алгебраических уравнений
Название: Численные методы решения систем линейных алгебраических уравнений Раздел: Рефераты по математике Тип: реферат Добавлен 07:31:10 24 июня 2011 Похожие работы Просмотров: 3515 Комментариев: 13 Оценило: 4 человек Средний балл: 5 Оценка: неизвестно Скачать | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
k | х1(k) | х2(k) | х3(k) |
0 | 1.0 | 2.0 | 2.0 |
1 | 1.75 | 3.375 | 3.0 |
2 | 1.84375 | 3.875 | 3.025 |
3 | 1.9625 | 3.925 | 2.9625 |
4 | 1.990625 | 3.9765625 | 3.0 |
5 | 1.99414063 | 3.9953125 | 3.0009375 |
… | … | … | … |
15 | 1.99999993 | 3.99999985 | 3.0009375 |
… | … | … | … |
19 | 2.0 | 4.0 | 3.0 |
Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19].
1.5 Итерация Гаусса-Зейделя
Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.
Отметим, что итеративный процесс Якоби производит три последовательности – <х1 (k) >, <х2 (k) >, <х3 (k) >, <х4 (k) >. Кажется разумным, что х1 (k+1) может быть использовано вместо х2 (k ). Аналогично х1 (k+1) и х2 (k+1) можно использовать в вычислении х3 (k+1) . Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):
Такой итерационный процесс даст результаты:
k | х1 (k) | х2 (k) | х3 (k) |
0 | 1.0 | 2.0 | 2.0 |
1 | 1.75 | 3.75 | 2.95 |
2 | 1.95 | 3.96875 | 2.98625 |
3 | 1.995625 | 3.99609375 | 2.99903125 |
… | … | … | … |
8 | 1.99999983 | 3.99999988 | 2.99999996 |
9 | 1.99999998 | 3.99999999 | 3.0 |
10 | 2.0 | 4.0 | 3.0 |
Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19].
1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):
Эти формулы как раз и задают собственно итерационный процесс.
2. При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать и более точно:
Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:
3. Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.
Глава 2. Применение численных методов для решения систем линейных алгебраических уравнений в теории и на практике
§1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Существуют два типа методов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем общего вида и варианты — метод прогонки и методы матричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от порядка системы n структуры матрицы.
При изучении итерационных методов мы трактуем систему уравнений как операторное уравнение первого рода Au = f и излагаем общую теорию итерационных методов для операторных уравнений при минимальных предположениях относительно оператора А. Общая теория позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γi > О и γ2 >= γ1 спектра оператора А в некотором энергетическом пространстве HD ; 2) для случая, когда границы γ1 и γ2 неизвестны. Весьма эффективным является попеременно-треугольный метод.
Основная задача линейной алгебры — решение системы уравнений
Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только тривиальное решение, и система (1) имеет единственноерешение
В курсе линейной алгебры решение системы (1) обычно выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа действий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определителя требует примерно такого же времени, что и решение системы линейных уравнений современными численными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к большим ошибкам округлений.
Особенность большинства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Основное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).
Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:
1) найти решение одной конкретной задачи (1);
2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для многовариантного расчета.
При многовариантном расчете можно уменьшить среднее число операций для одного варианта, если хранить некоторые величины, а не вычислять их заново для каждого варианта. Это, конечно, зависит от машины, от объема ее оперативной памяти.
При теоретических оценках качества алгоритмов их сравнение проводится по числу q ( e ) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].
Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последовательного исключения. Процесс решения системы линейных алгебраических уравнений Ax = f (1) по методу Гаусса состоит из двух этапов.
Первый этап (прямой ход). Система (1) приводится к треугольному виду
Метод квадратного корня. Этот метод пригоден для систем
с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение
где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=fсводится к последовательному решению двух систем
Метод квадратного корня требует порядка N 2 /3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.
1. Метод итераций для решения системы линейных алгебраических уравнений .
Перейдем к общему описанию метода итераций для системы линейных алгебраических уравнений
Для ее решения выбирается некоторое начальное приближение у0 H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации yh +1 выражается через известные предыдущие итерации yk , yk -1 ,… Если при вычислении yh +1 используется только одна предыдущая итерация yh , то итерационный метод называют одношаговым (или двухслойным) методом; если же yk +1 выражается через две итерации yk и yk -1 , то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H -> H — линейный оператор в конечномерном пространстве H со скалярным произведением (•, •).
Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный итерационный метод можно записать в следующей канонической форме:
(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В -1 , k — номер итерации, τ1 τ2 , . τk +1 , . — итерационные параметры, τk +1 > 0. Оператор В может, вообще говоря, зависеть от номера k — для Для простоты изложения мы предполагаем всюду, что В не зависит от k .
Если В = Е — единичный оператор, то метод(8) называют явным: yh +1 находится по явной формуле
В общем случае, при В≠ Е, метод (7) называют неявным итерационным методом: для определения yh +1 надо решить уравнение:
(9)
Естественно требовать, чтобы объем вычислений для решения .системы Byk +1 = Fk был меньше, чем объем вычислений для прямого решения системы Au=f
Точность итерационного метода (7) характеризуется величиной погрешности zh = ук — и, т. е. разностью между решением уравнения (7) и точным решением и исходной системы линейных алгебраических уравнений. Подстановка yk = zk + u в (2) приводит к однородному уравнению для погрешности:
§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
2.1 Общие сведения
К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы — алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.
2.2.1 Описание метода
Рассмотрим СЛАУ вида
Ax = B, где А — матрица. (1)
Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру
xk → x*, где х* — решение заданной системы.
В конечном варианте система будет имееть вид:
Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.
, или .
Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.
Для преобразования системы можно выполнить следующие операции:
В результате получим систему:
В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:
Итерационный процесс продолжается до тех пор, пока значения х1 ( k ), х2 ( k ), х3 ( k ) не станут близкими с заданной погрешностью к значениям х1 ( k -1), х2 ( k -1), х3 ( k -1).
2.2.2 Решение СЛАУ методом простых итераций
Решить СЛАУ методом простых итераций с точностью .
Для удобства преобразуем систему к виду:
,
Принимаем приближение на 0-ом шаге:
,
,
На 1-м шаге выполняем следующее:
Подставляем принятые приближения в первоначальную систему уравнений
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 2-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 3-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 4-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 5-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 6-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].
2.3 Метод Зейделя
2.3.1 Описание метода
В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения вычисляются по формулам:
Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).
Если данное условие выполнено, необходимо проследить, чтобы система была приведена к виду, удовлетворяющему решению методом простой итерации и выполнялось необходимое условие сходимости метода итераций:
, либо
2.3.2 Решение СЛАУ методом Зейделя
Решить СЛАУ методом Зейделя с точностью .
Эту систему можно записать в виде:
В этой системе сразу видно, что выполняется условие, где диагональные элементы матрицы коэффициентов по модулю больше, чем сумма модулей остальных элементов соответствующей строки.
Для удобства преобразуем систему к виду:
,
Принимаем приближение на 0-ом шаге:
На 1-м шаге выполняем следующее:
Подставляем принятые приближения в первоначальную систему уравнений
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 2-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 3-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 4-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить [9].
2.4 Сравнительный анализ
Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:
http://nsportal.ru/ap/library/nauchno-tekhnicheskoe-tvorchestvo/2014/02/09/chislennye-metody-resheniya-v-algebre-i-geometrii
http://www.bestreferat.ru/referat-238943.html