Методы решения систем линейных алгебраических уравнений

Приближённые методы решения систем линейных алгебраических уравнений. Интерполяция, аппроксимация; интерполяционный многочлен. Приближённое интегрирование функций. Численное решение трансцендентных, нелинейных и обыкновенных дифференциальных уравнений.

Рубрика Математика
Вид курс лекций
Язык русский
Дата добавления 26.09.2017
Размер файла 354,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.Allbest.ru/

Лекция 1. Приближённые методы решения систем линейных алгебраических уравнений

Пусть дана система n линейных уравнений с n неизвестными:

(1)

или где - заданные числа; .

Задаются произвольно n-чисел - нулевое приближение искомой функции.

Далее подставляем в правую часть системы (1) нулевое приближение и находим первое приближение.

, (2)

Затем по 1-ому приближению находят 2-ое, 3-е и т.д.

В результате для k-ого приближения получаем формулу:

, (2')

Таким образом, мы получили последовательность векторов

Х(0)(1),…, Х(К), к = 1,2

Если любая из таких последовательностей {Хi(к)} сходится некоторому пределу xik = ci , ,то данный вектор сi, является решением сист. (1)

В равенстве (2') перейдем к пределу при k>? при замене хi на сi.

Теорема (достаточные условия сходимости простой итерации):

Пусть выполняется хотя бы одно из следующих условий (нормы матрицы):

а) Если максимум суммы модулей коэффициентов при неизвестных (по строкам) меньше 1:

б) Если максимум суммы модулей коэффициентов при неизвестных (по столбцам) меньше 1:

в) Если сумма всех элементов в квадрате меньше 1.

Если выполняется хотя бы одно, тогда справедливы утверждения:

1) система (1) имеет единственное решение (С1,... Сn);

последовательность , где i = определяется по формуле (2), при любом начальном приближении сходится к соответствующим компонентам точного решения.

i =

2) для приближенного равенства верны оценки (x1(k),…xn(k))(C1,…Cn),

а') если выполняется условие а), то

,

б') если выполняется условие б), то

,

в') если выполняется условие в), то

Замечания:

1) Если нет никакой информации о точном решении СЛАУ, то за начальное приближение выбираем столбец свободных коэффициентов. (из приведенной матрицы);

2) остановка вычислений производной по заданной величине абсолютной погрешности и приведенным в теореме оценкам.

Б) Метод Зейделя

Этот метод является модификацией МПИ и заключается в том, что при вычислении (к+1) приближения неизвестного хi (i>1), используются уже вычисленные ранее (к+1) приближения неизвестных х1, х2,…, хi-1

Рассмотрим систему:

i = 1,n

Пусть матрица б удовлетворяет одному из условий теоремы:

Если, а) <1 (коэффициенты по строкам)

б) <1 (коэффициенты по столбцам)

в)<1 (все коэффициенты)

тогда общая формула метода Зейделя имеет вид:

к = 1,2…

Замечание: метод Зейделя обычно, но не всегда сходится к точному решения быстрее, чем МПИ

В) Метод Гаусса. (Метод последовательного исключения переменных)

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. aij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

Прямой ход

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

Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:

11 а12 … а1k … a1n | b1)

(0 a22 … a2k … a2n | b2)

(0 … … … … … )

(0 0 … akk … akn | bk)

(0 … … … … … )

(0 0 … ank … ann | bn)

Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте аnk ноль. Для этого коэффициент должен быть равен cnk=ank/akk. Элемент аkk называется разрешающим элементом k-ого шага и должен быть отличен от 0.

Формулы прямого хода

cmk = amk/akk, где 1< = k<n

bm = bm-cmkbk, k<m< = n

aml = aml-cmkakl, k< = l< = n

Обратный ход

Последовательное вычисление значения неизвестных xn, xn-1,..., х1 (именно в таком порядке) для полученной после прямого хода верхнетреугольной системы называется обратным ходом.

Формулы обратного хода

, откуда получаем:

для k = n,n-1,…,1.

Лекция 2. Интерполяция, аппроксимация

Интерполяционный многочлен

Предполагается, что функция задана в виде таблицы конечного числа точек:

х

х0

х1

хn

,

у

y0

y1

yn

например, получена экспериментально или по известной (достаточно сложной) формуле для . Здесь хi и yi (i = 0,1,…, n) - произвольные числа и при этом все хi различны и упорядочены: . При этом множество всех узлов хi называют сеткой, если узлы являются равноотстоящими, т.е. хi= х0+ih, где

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

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

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

Определение 1. Функция называется интерполяционной для , если выполнены условия: , i = 0,1, …, n, т.е. график проходит через все заданные точки .

Известно, что для данной таблицы всегда существует и притом единственны интерполяционный многочлен (ИМ) степени n. Будем обозначать ИМ через . Для него верно:

, i = 0,1, …, n (1)

Остаточный член для , т.е. величина , имеет вид:

(2)

где Пn+1(x) = (x-x0)(x-x1)…(x-xn).

Так как точка о практически всегда неизвестна, то при оценке погрешности для пользуются неравенством:

(2ґ)

А) ИМ Лагранжа имеет вид:

где (3)

В) ИМ Ньютона

ИМ Ньютона строятся на сетке и выражаются через конечные разности.

Определение 2. Величина называется конечной разностью первого порядка функции в точке с шагом h. По аналогии имеем: 2-ая конечная разность - это ,

k-ая конечная разность - это .

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

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

Таблица 1

xi

yi

Д yi

Д2 yi

Д3 yi

Д4 yi

x0

y0

Д y0

Д2 y0

Д3 y0

Д4 y0

x1

y1

Д y1

Д2 y1

Д3 y1

x2

y2

Д y2

Д2 y2

x3

y3

Д y3

x4

y4

1-ый ИМ Ньютона имеет вид:

(4)

ИМ Ньютона играет в численном анализе роль, аналогичную роли формулы Тейлора в математическом анализе. Так при использовании формулы (4), если слагаемые, начиная с какого-то номера становятся малыми, то ими пренебрегают.

Если ввести обозначение: t = (x-x0)/h, то 1-ый ИМ Ньютона примет вид:

(5)

0 ? t ? n; t=(x-x0)/h

Оценка погрешности:

; 0 ? t ? n; x є [x0; xn],

м = max¦f(n+1)(x)¦

Если ввести обозначение: t = (x-xn)/h, то получим 2-ый ИМ Ньютона:

(6)

- n ? t ? 0; t=(x-xn)/h

Оценка погрешности:

; -n ? t ? 0; x є [x0;xn],

м = max¦f(n+1)(x)¦

С) Метод наименьших квадратов

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

Предполагается, что функция задана в виде таблицы конечного числа точек

хi

х0

х1

хn

,

уi

y0

y1

yn

например, получена экспериментально,

где xi, yi (i = 1,…,n) - произвольные числа. При этом все числа xi различны.

Пусть также имеется некоторая функция , определенная для всех значений xi (i = 1,…, n).

Определение 3. Число Т, где

, (7)

называется среднеквадратичным (или среднеквадратическим) уклонением функции от заданной .

Наряду с числом Т вводят также вспомогательную величину

(8)

Функцию стараются подобрать, чтобы число Т получилось достаточно малым.

Можно предложить следующие способы выбора функции .

Способ 1

, (9)

т.е. - многочлен степени m, при этом m<n.

Способ 2

,

здесь - сплайн, т.е. кусочно-полиномиальная гладкая функция.

Способ 3

, (10)

т.е. - частичная сумма ряда Фурье, при этом m - четно и m<n.

Перечисленные способы 1-3 задают для вид приближающей функции , которая, в свою очередь, зависит от коэффициентов (или параметров) ai. Лучшим набором коэффициентов ai считается тот, для которого величина w из (8) меньше.

Определение 4. Говорят, что функция найдена для по методу наименьших квадратов (МНК), если она дает минимально возможное значение величины w в соотношении (8).

Примечание. Заметим, что при m=n-1 многочлен , полученный по МНК, совпадает с интерполяционным многочленом и, следовательно, соответствующее среднеквадратичное уклонение (теоретически) равно числу . При использовании в расчетах ЭВМ это уклонение, как правило, получается числом, отличным от нуля.

Рассмотрим в качестве приближающей функции многочлен степени m, который имеет вид

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

То есть функция коэффициентов . Наряду с функцией Т рассматривают функцию S вида:

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

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

(11)

Используя необходимое условие экстремума функции нескольких переменных, получим систему для определения коэффициентов , где :

(12)

То есть:

(13)

Лекция 3. Приближённое интегрирование функций

Общие замечания

Если функция f(x) непрерывна на отрезке [a, b] и известна её первообразная F(x), то определённый интеграл от этой функции в пределах от a до b может быть вычислен по формуле Ньютона- Лейбница

, (1)

где F?(x) = f(x).

Однако во многих случаях первообразная функция F(x) не может быть найдена с помощью элементарных средств или является слишком сложной; вследствие этого вычисление определённого интеграла по формуле (1) может быть затруднительным или даже практически невыполнимым.

Кроме того, на практике подынтегральная функция f(x) часто задаётся таблично или графически. Поэтому важное значение имеют приближённые и в первую очередь численные методы вычисления определённых интегралов.

Задача численного интегрирования функции заключается в вычислении значения определённого интеграла на основании ряда значений подынтегральной функции.

Обычный приём при численном вычислении однократных интегралов.

Отрезок [a, b] разбивают на части (чаще всего равные) точками хj (j =) так, что a = x0 < x1 < x2…< xn = b, и в узлах хj находят значения уj = f(xj). Функцию f(x) заменяют интерполирующей или аппроксимирующей функцией простого вида (например, полином) такой, что она легко интегрируется.

Мы получаем квадратурные формулы:

, (2)

где хj ? выбранные узлы интерполяции,

Аj ? коэффициенты, зависящие только от выбора узлов, но не от вида функции, R ? остаточный член, или погрешность квадратурной формулы.

1) Интегрирование по методу прямоугольников

Метод прямоугольников ? простейший приём численного интегрирования, при котором функция f(x) заменяется интерполяционным многочленом нулевого порядка. Интервал интегрирования [a,b] делится точками х0, х1, …, хn на n равных частей (рис. 1), причём х0 = a, xn= b, длина каждой части составляет h = (b-a)/n, и тогда xi = x0+ih, i = 0, …, n.

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

Рис. 1. Геометрическая интерпретация интегрирования по методу прямоугольников

Площадь полученной ступенчатой фигуры можно найти как сумму площадей прямоугольников, стороны которых равны h и уi. Следовательно, площадь отдельного прямоугольника составит Si = yi•h, тогда

Следовательно, формула вычисления определённого интеграла по методу прямоугольников имеет вид:

(3)

Остаточный член имеет вид:

(4)

2) Интегрирование по методу трапеций

Метода трапеций заключается в линейной аппроксимации f(x) на отрезке [a,b]. Участок интегрирования также разбивается на n равных частей. Если провести ординаты во всех точках деления и заменить каждую из полученных криволинейных трапеций прямолинейной (рис.2), то приближённое значение интеграла будет равно сумме площадей прямолинейных трапеций.

Рис. 2 Геометрическая интерпретация интегрирования по методу трапеций

Площадь отдельной трапеции составляет:

,

Тогда площадь искомой фигуры будем искать по формуле:

Следовательно, формула трапеций для численного интегрирования имеет вид:

(5)

Остаточный член имеет вид

(6)

На практике для оценки абсолютной погрешности формулы трапеций применяют следующие соотношения:

1. , (7)

При этом, как правило, получают для завышенную оценку.

2. Правило Рунге (n ? чётное) даёт более тонкую оценку :

(8)

Но при этом может получиться для заниженная оценка, чего следует опасаться.

3) Интегрирование по методу Симпсона

Пусть n = 2m ? чётное число, а уi = f(xi) (i = 0..n) ? значения функции у = f(x) для равноотстоящих точек a = x0, x1, x2, …, xn = b с шагом h =(b-a)/n = (b-a)/2m. На паре участков (рис.3) кривая у = f(x) заменяется параболой у = L(x), коэффициенты которой подобраны так, что она проходит через точки у0, у1, у2.

Рис.3 Геометрическая интерпретация интегрирования по методу Симпсона

Площадь криволинейной трапеции, ограниченной сверху параболой, составит:

Суммируя площади всех криволинейных трапеций, получим:

Где p = 6-p, p = 4. Следовательно, формула Симпсона для численного интегрирования имеет вид:

(9)

Остаточный член имеет вид:

(10)

На практике для оценки абсолютной погрешности формулы Симпсона применяют следующие соотношения:

1. ,

(11)

При этом, как правило, получают для завышенную оценку.

2. Правило Рунге (n ? чётное) даёт более тонкую оценку :

(12)

Но при этом может получиться для заниженная оценка, чего следует опасаться.

Формулы прямоугольников и трапеций дают точное значение интеграла, когда подынтегральная функция f(x) линейна, ибо тогда f ?(x) = 0, а формула Симпсона является точной для многочленов до третьей степени, т. к. в этом случае f (4) = 0.

Если функция у = f(x) задана таблично и её производные найти затруднительно, то в предполо- жении отсутствия быстро колеблющихся составляющих можно применить приближённые формулы для погрешностей, выраженные через конечные разности:

(*)

(**)

Выбор шага

1. Пусть требуется вычислить интеграл с точностью е. Используя формулу соответствующего остаточного члена R, выбирают h таким образом, чтобы выполнялось неравенство .

2. Двойной пересчёт. ( Правило Рунге).

Лекция 4. Численное решение трансцендентных и нелинейных уравнений

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

Процесс нахождения приближённых значений корней уравнения:

f(x) = 0, (1)

где функция f(x) определена и непрерывна в некотором конечном или

бесконечном интервале a < x < b разбивается на два этапа:

1) отделение корней;

2) уточнение корней до заданной степени точности.

2.1 Отделение корней

Всякое значение л, обращающее функцию f(x) в нуль, т. е. такое, что f(л) = 0, называется корнем уравнения (1) или нулём функции f(x).

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

Графический метод отделения корней: a) строят график функции у = f(x) для уравнения вида f(x) = 0. Значения действительных корней уравнения являются абсциссы точек пересечения графика функции у = f(x) с осью Ох (рис.1);

b) представляют уравнение (1) в виде ц(х) = g(x) и строят графики функций

у = ц(х) и у = g(x). Значения действительных корней уравнения являются абсциссы точек пересечения графиков функций у = ц(х) и у = g(x) (рис.2).

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

Размещено на http://www.Allbest.ru/

Рис.1 Рис.2

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

Уточнение корней до заданной точности

То есть сужение отрезка локализации корня [a,b]. Рассмотрим несколько методов.

1) Метод половинного деления (дихотомии)

Пусть корень отделён и принадлежит отрезку . Находим середину отрезка по формуле (рис.3). Если , то с - искомый корень.

Рис. 3

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

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

После каждой итерации отрезок, на котором расположен корень уменьшается вдвое, то есть после n итераций он сокращается в 2n раз. Таким образом, число итераций n в данном методе зависит от предварительно заданной точности е и от длины исходного отрезка и не зависит от вида функции f(x). Это является важным преимуществом метода половинного деления по сравнению с другими методами. Метод, однако, медленно сходится при задании высокой точности расчёта.

2) Метод хорд

Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ?(x) и f ?(x) сохраняют постоянный знак на интервале (a,b). Тогда возможны четыре случая расположения дуги кривой (рис. 4).

Рис. 4

В методе хорд за очередное приближение берём точку пересечения с осью Х прямой (рис.5), соединяющей точки (a,f(a)) и (b,f(b))

Причём одна из этих точек фиксируется ? та, для которой знаки f(x) и f ?(x) одинаковы.

Для рис. 5 неподвижным концом хорды является х =a.

Уравнение хорды АВ:

Точка пересечения хорды с осью Х (у=0):

Теперь корень находится на отрезке [a,c1]. Заменяем b на с1.

Рис. 5. Иллюстрация метода хорд

Применяя метод хорд к этому отрезку, получим:

Продолжим и т.д., получим:

(2) Условие окончания вычислений:

¦сn+1 ? cn¦< е или ¦f(cn)¦< е1.

Для оценки погрешности можно пользоваться общей формулой:

, где

Итак, если f (x)•f?(x) > 0, то приближённое значение корня находят по формуле (2), если f?(x)•f?(x) < 0 (т.е. фиксируется х = b), то по формуле:

. (3)

2) Метод Ньютона (касательных).

Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ?(x) и f ?(x) сохраняют постоянный знак на интервале (a,b).

Геометрический смысл метода касательных состоит в том, что дуга кривой y = f(x) заменяется касательной к этой кривой.

Рис. 7. Иллюстрация метода касательных

Выберем в качестве начального приближения х0 = a и проведём в точке А0(a,f(a)) касательную к графику функции f(x). Абсцисса пересечения касательной с осью Ох (у = 0) является первым приближением к корню (рси.7):

или х0 =

Через точку А11;f(x1)) снова проведём касательную, абсцисса точки пересечения которой даст второе приближение х2 корня о и т.д. Очевидно, что в точке Аn(xn;f(xn)):

y ? f(xn) = f ?(xn)(x?xn)

и алгоритм метода Ньютона запишется так:

(4)

Заметим, что в нашем случае, если положить х0 = b и провести касательную к кривой у = f(x) в точке b, то первое приближение не принадлежит отрезку [a,b].

Таким образом, в качестве начального приближения х0 выбирается тот конец интервала [a,b], для которого знаки f(x) и f ?(x) одинаковы

Условие окончания вычислений:

¦сn+1 ? cn¦< е или ¦f(cn)¦< е1.

Для оценки погрешности можно пользоваться общей формулой

, где

4) Комбинированный метод (хорд и касательных)

Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, и уточнение корня происходит быстрее. Пусть дано уравнение f(x) = 0, корень о отделён и находится на отрезке [a,b]. Применим комбинированный метод хорд и касательных с учётом типа графика функции (рис. 4).

Если f (x)?f ?(x) < 0 (рис.4 в, г), то методом хорд получаем значение корня с избытком, а методом касательных - с недостатком.

Если f (x)?f ?(x) > 0 (рис.4 а, б), то метод хорд даёт приближение корня с недостатком, а метод касательных - с избытком.

Рассмотрим случай, когда f (b) < 0, f ?(x) > 0 (рис.8), то со стороны конца а лежат приближённые значения корня, полученные по методу касательных, а со стороны конца b - значения, полученные по методу хорд.

Рис. 8. Иллюстрация комбинированного метода

Тогда ,

Теперь истинный корень о находится на интервале [a1,b1]. Применяя к этому интервалу комбинированный метод, получаем

,

и вообще

, . (5)

Для случая, когда f (b)?f ?(x) > 0, то рассуждая аналогично, получим следующие формулы для уточнения корня уравнения:

, . (6)

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

|bn+1-an+1| < е.

Корень уравнения есть среднее арифметическое последних полученных значений: о = (an+1+bn+1)/2

линейный алгебраический трансцендентный дифференциальный

Лекция 5. Приближённое решение обыкновенных дифференциальных уравнений и систем обыкновенных дифференциальных уравнений

Пусть функция у = f(x,y) отражает количественную сторону некоторого явления. Рассматривая это явление, мы можем установить характер зависимости между величинами х и у, а также производными от у по х, т.е. написать дифференциальное уравнение.

Определение: Обыкновенным дифференциальным уравнением называется уравнение, связывающее независимую переменную х, искомую функцию y = f(x) и её производные.

Запись:

F( x, y, y?, y??,…, y(n)) = 0 или .

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

у?-2ху3+5 = 0 - уравнение первого порядка,

у?+ky?-by-sinx = 0 - уравнение второго порядка.

Задача Коши (для уравнения первого порядка):

у? = f(x, y) (1) найти решение y = y(x),

удовлетворяющее начальному условию: у(х0)=у0. (1*).

Т.е. найти интегральную кривую, проходящую через точку М(х0, у0).

Если f(x,y) непрерывна в области R: |x-x0| < a, |y-y0| < b, то существует по меньшей мере одно решение у = у(х), определённое в некоторой окрестности: |х-х0| < h, где h Ї положительное число. Это решение единственно, если в R выполнено условие Липшица:

(2)

Где NЇ постоянная (константа Липшица), зависящая в общем случае от a и b. Если f(x,y) имеет ограниченную производную в R, то можно положить:

Для дифференциального уравнения n-го порядка: у(n)=f(x,y,y?,…,y(n-1)) задача Коши состоит в нахождении решения у = у(х), удовлетворяющего начальным условиям:

у(х0) = у0, у?(х0) = у?0, …, у(n-1)(x0) = y(n-1)0 Ї заданные числа.

Функция у = f(x, C1, C2,…, Cn), где С1,…, СnЇ произвольные постоянные, называется общим решением ОДУ или общим интегралом.

Эти постоянные можно определить с помощью начальных условий. Решение ДУ при заданных начальных условиях называется его частным решением.

Определение: задача называется краевой, если указывается интервал интегрирования [a,b] и ставятся дополнительные условия для значений функции у и её производных на концах этого интервала.

Процесс познания закономерностей и стремление создать детальную картину исследуемых явлений приводит к более сложной количественной оценке, отражающей эти явления, а именно к функции многих переменных, зависящих как от пространственных координат, так и от времени u = f(x1, x2,…, xn, t).

Определение: Дифференциальным уравнением с частными производными называется уравнение, связывающее независимую переменные х1, х2, …, хn, t, искомую функцию

u = f (х1, х2, …, хn, t) и её частные производные:

Постановка задачи

Дано дифференциальное уравнение первого порядка: у? = f(x,y) (1).

Требуется найти решение этого уравнения на отрезке [x0, xmax], удовлетворяющее начальным условиям: у(х0) = у0 (2).

В вычислительной практике более предпочтительным являются численные методы нахождения приближённого решения в фиксированных точках: х0<x1<…<xn=xmax.

Большинство численных методов решения задачи (1) с начальными условиями (2) можно привести к виду:

(3)

Ї при r = 1, а1 = 1, b0 = 0 методы вида (3) называются одношаговыми ( чтобы найти yi+1

требуется информация только о предыдущей точке (xi, yi)).

Ї при r > 1 и b0 = 0 Ї явными многошаговыми.

Ї при r > 1 и b0 ? 0 Ї неявными многошаговыми.

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

А) Метод Эйлера

Для решение Д.У.(1) с Н.У. (2) на отрезке [x0, xmax] по методу Эйлера, таблица приближённых значений у(х) для равноотстоящих узлов: строится по формулам:

yk+1 = yk + h•f(xk,yk)

xk+1 = xk + h, k = 0,…,n-1, h=(xn-x0)/n (4)

х

x0

x1

хn

y

y0

y1

yn

Абсолютная погрешность формулы (4) на каждом шаге имеет порядок h2

(5)

Формула (4) означает, что на отрезке [xk, xk+1] интегральная кривая y = y(x) приближённо заменяется прямолинейным отрезком, выходящим из точки М(хkk) с угловым коэффициентом f(хkk). В качестве приближения искомой интегральной кривой получаем ломаную линию с вершинами в точках М000), М111),…, Мnnn). Первое звено касается истинной интегральной кривой в точке М000).

Метод Эйлера может быть применён к решению системы ОДУ и ДУ высших порядков. Последние должны быть предварительно приведены к системе ОДУ первого порядка. Пусть задана система ОДУ первого порядка:

(6)

с начальными условиями: у(х0) = у0, z(х0) = z0 (7)

Приближённые значения у(хi) ? yi, z(хi) ? zi вычисляются по формулам:

(8)

Метод Эйлера обладает двумя существенными недостатками:

1) малой точностью (метод первого порядка точности);

2) систематическое накопление ошибок.

В) Модификации метода Эйлера.

1ый усовершенствованный метод Эйлера

Сначала вычисляют промежуточные значения:

(9)

А затем полагают:

(10)

2oй усовершенствованный метод Эйлера

Сначала определяют «грубые приближения»:

(11)

И приближённо полагают:

(12)

Локальная погрешность на i-ом шаге: .

Оценка погрешности в точке хn может быть получена с помощью двойного просчёта (с шагом h и h/2):

(13)

С) Метод Рунге-Кутта. (4го порядка)

Наиболее знаменитым из методов Рунге-Кутта является классический метод 4го порядка

(14)

(15)

Грубая оценка погрешности (двойной просчёт):

(16)

Где у(хi) - точное решение, у*i - приближённое решение с шагом h/2, yi - … с шагом h .

Для оценки правильности выбора шага h используют равенство:

(17)

q должно равняться нескольким сотым, иначе h уменьшается.

D) Метод Рунге-Кутта 3-го порядка

Многошаговые методы

(используют информацию о нескольких предыдущих точках)

Д) Алгоритм Адамса

Пусть дано дифференциальное уравнение: у? = f(x, y) (1)

с начальными условиями: у(х0) = у0 (1*)

Требуется найти решение уравнения (1) на отрезке [a,b].

Разобьём отрезок [a,b] на n равных частей точками хi = х0 + ih (i =0, 1, …, n).

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

Следовательно, определены: у1, у2, …, уk-1 в точках: х0 + h, …, x0 + h(k-1).

2ойэтап: рекурсивной процедуры. Определение: уk, yk+1,…, yn основано на интегрировании интерполяционного многочлена Ньютона.

Рабочие формулы явных методов Адамса (2-го, 3-го, 4-го порядков).

(2)

(3)

Формулы (2)-(4) называются экстраполяционными и на практике используются в качестве прогноза.

Для улучшения точности или коррекции результата применяют неявные методы (используют ещё ненайденные значения: уk+1, yk+2,…).

(5)

(6)

(7)

Формулы (5)-(7) называются интерполяционными.

Для грубой оценки точности (двойной просчёт):

Размещено на Allbest.ru

...

Подобные документы

  • Решение систем линейных алгебраических уравнений методом исключения Гаусса. Табулирование и аппроксимация функций. Численное решение обыкновенных дифференциальных уравнений. Приближенное вычисление определенных интегралов. Решение оптимизационных задач.

    курсовая работа [1,6 M], добавлен 21.11.2013

  • Приближенные числа и действия над ними. Решение систем линейных алгебраических уравнений. Интерполирование и экстраполирование функций. Численное решение обыкновенных дифференциальных уравнений. Отделение корня уравнения. Поиск погрешности результата.

    контрольная работа [604,7 K], добавлен 18.10.2012

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

    методичка [899,4 K], добавлен 01.12.2009

  • Изучение основ линейных алгебраических уравнений. Нахождение решения систем данных уравнений методом Гаусса с выбором ведущего элемента в строке, в столбце и в матрице. Выведение исходной матрицы. Основные правила применения метода факторизации.

    лабораторная работа [489,3 K], добавлен 28.10.2014

  • Изучение способов решения нелинейных уравнений: метод деления отрезка пополам, комбинированный метод хорд и касательных. Примеры решения систем линейных алгебраических уравнений. Особенности математической обработки результатов опыта, полином Лагранжа.

    курсовая работа [181,1 K], добавлен 13.04.2010

  • Сущность итерационного метода решения задачи, оценка его главных преимуществ и недостатков. Разновидности итерационных методов решения систем линейных алгебраических уравнений: Якоби, Хорецкого и верхней релаксации, их отличия и возможности применения.

    курсовая работа [39,2 K], добавлен 01.12.2009

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

    реферат [60,6 K], добавлен 15.08.2009

  • Методы решения систем линейных алгебраических уравнений (СЛАУ): Гаусса и Холецкого, их применение к конкретной задаче. Код программы решения перечисленных методов на языке программирования Borland C++ Builder 6. Понятие точного метода решения СЛАУ.

    реферат [58,5 K], добавлен 24.11.2009

  • Решение систем линейных алгебраических уравнений методом простой итерации. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями. Среднеквадратическое приближение функции. Численное интегрирование функций методом Гаусса.

    курсовая работа [2,4 M], добавлен 14.04.2009

  • Формирование системы их пяти уравнений по заданным параметрам, ее решение методом Гаусса с выбором главного элемента. Интерполяционный многочлен Ньютона. Численное интегрирование. Решение нелинейных уравнений. Метод Рунге-Кутта четвертого порядка.

    контрольная работа [115,5 K], добавлен 27.05.2013

  • Методы численного интегрирования, основанные на том, что интеграл представляется в виде предела суммы площадей. Геометрическое представление метода Гаусса с двумя ординатами. Численные примеры и сравнение методов. Решение систем алгебраических уравнений.

    курсовая работа [413,4 K], добавлен 11.06.2014

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

    реферат [66,4 K], добавлен 14.08.2009

  • Решение задач вычислительными методами. Решение нелинейных уравнений, систем линейных алгебраических уравнений (метод исключения Гаусса, простой итерации Якоби, метод Зейделя). Приближение функций. Численное интегрирование функций одной переменной.

    учебное пособие [581,1 K], добавлен 08.02.2010

  • Структура и элементы, принципы формирования и правила разрешения систем линейных алгебраических уравнений. История развития различных методов решения: матричного, Крамера, с помощью функции Find. Особенности применения возможностей программы Mathcad.

    контрольная работа [96,0 K], добавлен 09.03.2016

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

    реферат [111,8 K], добавлен 09.06.2011

  • Метод Зейделя как модификация метода простой итерации. Особенности решения систем линейных алгебраических уравнений. Анализ способов построения графика функций. Основное назначение формул Симпсона. Характеристика модифицированного метода Эйлера.

    контрольная работа [191,3 K], добавлен 30.01.2014

  • Понятие и специфические черты системы линейных алгебраических уравнений. Механизм и этапы решения системы линейных алгебраических уравнений. Сущность метода исключения Гаусса, примеры решения СЛАУ данным методом. Преимущества и недостатки метода Гаусса.

    контрольная работа [397,2 K], добавлен 13.12.2010

  • Задачи вычислительной линейной алгебры. Математическое моделирование разнообразных процессов. Решение систем линейных алгебраических уравнений большой размерности. Метод обратной матрицы и метод Гаусса. Критерии совместности и определенности системы.

    курсовая работа [220,0 K], добавлен 21.10.2011

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

    курсовая работа [508,1 K], добавлен 16.12.2015

  • Решение задач систем линейных алгебраических уравнений, матричных уравнений, методы Гаусса и Кремера. Нахождение длины и координат вектора и исчисление его скалярного произведения. Уравнение прямой и определение координат точек неравенства; пределы.

    контрольная работа [220,9 K], добавлен 06.01.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.