Билет № 25.

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

2). Решение линейных обыкновенных дифференциальных уравнений численно-аналитическим методом.

Решение линейных обыкновенных дифференциальных уравнений численно-аналитическим методом.

- начальное условие задачи

В качестве решения – функция (график) – дифференциальная кривая

-

дифференциальное уравнение n-ного порядка

В основном возникают задачи решения 1-ого порядка

Систем уравнений могут быть линейными и нелинейными. Линейные системы – это частный случай.

Метод решения:

Запись Коши:

Решение ищется в виде суммы общего решения однородной системы + частного решения неоднородной системы

Общее решение однородной системы в явной форме:

; ;

1. 

;

Система устойчива, если все ее члены отрицательны

2. - любая таблично заданная функция

;

При t=1 и x₀=k можно найти k

В неявной форме:

1. 

2. 

Теперь получаем снова произведение и решаем дальше

Дифференциальное уравнение второго порядка:

Частное решение находится точно также

Методы решения нелинейного уравнения (деление отрезка пополам, метод хорд, интерполяционный методы)

метод хорд

Пусть f(a)f(b)<0. Сущность метода состоит в замене кривой y=f(x)  хордами, проходящими через концы отрезков, в которых f(x)  имеет противоположные знаки. Метод хорд требует, чтобы один конец отрезка, на котором ищется корень, был неподвижен. В качестве неподвижного конца х₀ выбирают тот конец отрезка, для которого знак f(x)  совпадает со знаком второй производной.

Расчетная формула имеет вид 

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

[a,b] U*a+ =f(a)

[x1,b] U*b+ =f(b)

[x2,b]

[x3,b]

x1=a-f(a) (a-b)/( f(a)-f(b))

x₁b

x₂

а x₃метод прекращается когда |f(x_i)|<eps

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

этот метод сходится быстрее, чем метод деления интервала пополам

достоинства:

• простота

недостатки:

• функция должна быть гладкой

• условия на дифференцирование

Билет № 26.

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

2). Решение систем линейных алгебраических уравнений с разреженными матрицами, метод диагональной модификации.

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

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

Также, численные методы решения можно разделить на

• Конечно-разностные (обычные, рассматриваемые нами)

• Методы типа Ронге-Кутта

Можно выделить явные и неявные методы решения задачи. Примерами явных методов могут быть явный метод Эйлера, разложение в ряд Тейлора, а примерами неявных методов – метод Ньютона и неявный метод Эйлера.

Необходимо достичь стационарного состояния, когда решение уже не зависит от времени.

Численно устойчивый метод – если при h→∞, численное решение будет стремиться к истинному решению

Разложение в ряд Тейлора

- ряд Фурье

Общая формула явных численных методов решения дифференциальных уравнений

Явный метод Эйлера

Многошаговый метод надо разгонять

Чем больше p, тем больше можно использовать h, однако p больше 5 использовать не выгодно. Это экстраполяционный процесс.

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

• Локальной погрешности

• Численной неустойчивости

Таким образом шаг ограничен локальной погрешностью интегрирования

Пусть дано:

Протестируем на этой задаче явный метод Эйлера:

Условие численной устойчивости – главное условие

В среднем потребуется около 10²⁴ шагов, чтобы дойти до конца

Выводы:

1. Явные способы решения можно представить с помощью Метода Эйлера и ряда Тейлора

2. Все численные методы решения систем дифференциальных уравнений определяют решение по шагам, причем явные методы построены по схеме, когда неизвестная величина находится только в одной части уравнения, а неявные – когда неизвестная величина x(t_i) находится и в левой, и в правой частях.

• все неявные методы до 4 порядка устойчивы

Неявный метод порядка i имеет такую же точность, как явный метод порядка (i+1)

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

Ax=Y;

* *

* - матрица заполнена коэффициентами меньше чем на 10%,все остальное 0

* *

матрицу будем считать разреженной, если этот факт даст повышение эффективности вычислений

если k<<n,то тогда можно не выполнять операции, результат которых заранее известен

метод Гаусса:

в процессе работы в матрице появляются новые ненулевые элементы

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

(n!)² – количество перестановок, где n-разряд

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

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

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

количество ненулевых элементов при работе по методу Гаусса увеличивается примерно в 2-9 раз.

критерии упорядочивания:

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

2. проводится пробное разложение- берется строка с наименьшим количеством элементов, делаем один шаг разложения

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

.

а

δ x = Y (A+ ΔA) (x +Δx) = Y; (1)

с B U

.

Ax + A Δx + ΔA x + ΔA Δx = Y; (сокращается)

(A+ ΔA) Δx = -ΔAx;

i

ΔA= q i = i 1 1 *q

(A + ΔA) Δx = - e_ix_iq_i

B

V= Δx x_i^-1 q_i^-1

BV= -e_i;(2)

Δx= V x_iq_iU= x+ Δx;

U_i= x_i + δ_ix_iq

x_i= U_i/(1+δ_iq)

x= U + VqU_i/(1+δ_iq) – истинное решение