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

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

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

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

определена и непрерывна на отрезке a

, обращающее в нуль (т.е. ) является корнем уравнения

Алгоритм решения:
Отделение корней
Уточнение приближенных значений корней

x1 - x2 - x3- … - xn - b],

на которых произведение f(x(i)*f(x(i+1))<0

x1

x2

x3

Уточняем значение корня на каждом из выделенных участков [x(i) - x(i+1)]

отрезке [a,b] и имеет только один корень x*.
ε, δ

– малые значения, b>a.
Шаг1: Вычисляем значения функции f(x) на концах интервала - f(a), f(b).
Шаг2: Определяем середину интервала xср=(a+b)/2 и вычисляем в этой точке значение функции f(xср )
Шаг3: Вычисляем произведение –
f(a)* f(xср ).
Если f(a)* f(xср )<0, то присваиваем b=xср, иначе присваиваем a=xср
Шаг4: Признак завершения счета. Если abs(b-a)<δ, то перейти
к шагу 5,
иначе перейти к шагу 2.
Шаг5: Вычисляем x*=(a+b)/2 и f(x*)

b

a
x1 xср x2
b
F(x1)
F(x2)
F(x2)
F(x1)

[a,b] и имеет только один минимум. ε, δ – малые

значения, b>a.
Шаг1: Определяем середину интервала xср=(a+b)/2 , выделяем две точки на оси аргументов x1= xср – ε и x2= xср + ε .
Шаг2: Вычисляем в этих точках значения функции F(x1) и F(x2 ).
Шаг3: Сравниваем значения функции F(x1) и F(x2 ). Если F(x1) < F(x2 ), то присваиваем b= xср, иначе a= xср .
Шаг4: Завершение счета. Если
abs(b-a)< δ, то перейти к шагу 5, иначе перейти к шагу 2.
Шаг5: Вычисляем xmin=(a+b)/2 и F(xmin)

ε, δ – малые значения , b>a.

Поиск минимума функции одной

переменной: деление отрезка пополам.

функции

a

X1

X

ср

X2

b

F(x2)

F(xср)

F(x1)>F(xср)

Возможные

положения минимума функции

F(x2)

a

X1

X

ср

X2

b

F(x)

2

F(x

ср)

F(x1)>f(xср)

Возможные

положения минимума функции

F(x2)>F(xср)

A

X1

X

ср

X2

B

x1= xср – abs(b-a)/4 и
x2= xср + abs(b-a)/4 .

Шаг3: Вычисляем в этих точках значения функции F(xср), F(x1) и F(x2 ).
Шаг4: Сравниваем значения функции F(x1) и F(xср ). Если F(x1) < F(xср ), то присваиваем b= xср, xср=x1 и переходим к шагу 6, иначе переходим к шагу 5.
Шаг5: Сравниваем значения функции F(x2) и F(xср ). Если F(x2) < F(xср ), то присваиваем a= xср, xср=x2,
иначе присваиваем a= x1, b= x2
Шаг6: Завершение счета. Если abs(b-a)< δ, то перейти к шагу 7,
иначе перейти к шагу 2.
Шаг7: Вычисляем xmin=(a+b)/2 и F(xmin)

Xср, Xср=x2
a= X1, b=X2
Xmin, F( Xmin)

заключается в следующем. Дан отрезок AB


Отношение отрезков определяется соотношением AC/AB=CB/AC,

т.е. отношение большего отрезка к целому равно отношению меньшего отрезка к большему отрезку. Если принять целый отрезок АВ=1, то АС≈0.62, а СВ≈0.38.
Пусть функция F(x) задана на отрезке [a,b]
и имеет только один минимум.
ε, δ – малые значения.

А

С

В

функции
a
V
W
b

Выделяем две точки на оси аргументов v=L*k1 и w=L*k2 .
Шаг3:

Если b-a < δ , то перейти к шагу 9,
иначе перейти к шагу 4
Шаг4: Вычисляем значения F(v) и F(w).
Шаг5: Сравниваем значения F(w) и F(v ).
Если F(w) < F(v ), то присваиваем a=v, v=w и w:=a+(b-a)*k2; иначе переходим к шагу 7.
Шаг6: Присваиваем F(v )= F(w) и вычисляем новое значение F(w) и переходим к шагу 3.
Шаг7: Присваиваем b=w, w=v и v:=a+(b-a)*k1.
Шаг8: Присваиваем F(w )= F(v) и вычисляем новое значение F(v) и переходим к шагу 3.
Шаг9: Вычисляем xmin=(a+b)/2 и F(xmin)

функция, описывающая (n+1)-мерную поверхность.

только от x - F(x,y1)
Шаг 2: находим минимум F(x,y1) в

точке x1.
Шаг 3:Фиксируем значение x1. Функция F(x,y) зависит только от y - F(x1,y)
Шаг 4: находим минимум F(x1,y) в точке y2.
Шаг 5: Фиксируем значение y2. Функция F(x,y) зависит только от x - F(x,y2)
Шаг 6: находим минимум F(x,y2) в точке x2.
Шаг 7:Фиксируем значение x2. Функция F(x,y) зависит только от x - F(x2,y)
Шаг 8: находим минимум F(x2,y) в точке y3.
Условия выхода:
Значения функции F(x,y) на двух соседних итерациях меньше малого числа ε
Интервал между локальными минимумами на двух соседних итерациях меньше малого числа δ

f(x,y) по направлению x
Проверка на глобальный минимум
да
нет
выход

f(x,y)
Обращение к процедуре поиска минимума функции одной переменной (деление отрезка

пополам)

Функция f(x,y) записывается как function

Возврат в вызывающую программу

функции

функции F(x,y).
Шаг 2: Проводим сечение поверхности в плоскости вектора

градиента функции
Шаг 3: Проводим спуск вдоль линии сечения в направлении противоположном градиенту и находим локальный минимум одномерной функции
Шаг 4: и далее
Повторяем последовательность шагов 1-3 для каждой найденной точки локального минимума.
Условия выхода:
Значения функции F(x,y) на двух соседних итерациях меньше малого числа ε
Интервал между локальными минимумами на двух соседних итерациях меньше малого числа δ