Разделы презентаций


Численные методы ( язык Си )

Содержание

Численные методы (язык Си)Тема 1. Решение уравнений© К.Ю. Поляков, 2008-2009

Слайды и текст этой презентации

Слайд 1Численные методы (язык Си)
© К.Ю. Поляков, 2008-2009
Решение уравнений
Вычисление площади (интеграла)
Вычисление длины

кривой
Оптимизация

Численные методы (язык Си)© К.Ю. Поляков, 2008-2009Решение уравненийВычисление площади (интеграла)Вычисление длины кривойОптимизация

Слайд 2Численные методы (язык Си)
Тема 1. Решение уравнений
© К.Ю. Поляков, 2008-2009

Численные методы (язык Си)Тема 1. Решение уравнений© К.Ю. Поляков, 2008-2009

Слайд 3Основные понятия
Типы решения:
аналитическое (точное, в виде формулы)

приближенное (неточное)
Задача: решить уравнение
численные

методы
начальное приближение
при N  

Основные понятияТипы решения:аналитическое (точное, в виде формулы)приближенное (неточное)Задача: решить уравнениечисленные методыначальное приближениепри N  

Слайд 4Численные методы
Идея: последовательное уточнение решения с помощью некоторого алгоритма.
Область применения:

когда найти точное решение невозможно или крайне сложно.
можно найти хоть

какое-то решение
во многих случаях можно оценить ошибку (то есть можно найти решение с заданной точностью)

нельзя найти точное решение


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

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

Слайд 5Есть ли решение на [a, b]?
есть решение
нет решения
нет решения

Есть ли решение на [a, b]?есть решениенет решениянет решения

Слайд 6Метод дихотомии (деление пополам)
Найти середину отрезка [a,b]: c

= (a + b) / 2;
Если f(c)*f(a)

интервала b = c;
Если f(c)*f(a)≥ 0, сдвинуть левую границу интервала a = c;
Повторять шаги 1-3, пока не будет b – a ≤ .
Метод дихотомии (деление пополам)Найти середину отрезка [a,b]:    c = (a + b) / 2;Если

Слайд 7Метод дихотомии (деления пополам)
простота
можно получить решение с заданной точностью (в

пределах точности машинных вычислений)
нужно знать интервал [a, b]
на интервале [a,

b] должно быть только одно решение
большое число шагов для достижения высокой точности
только для функций одной переменной
Метод дихотомии (деления пополам)простотаможно получить решение с заданной точностью (в пределах точности машинных вычислений)нужно знать интервал [a,

Слайд 8Метод деления отрезка пополам
//----------------------------------------------
// BinSolve находит решение на [a,b]
//

методом деления отрезка пополам
// Вход: a,

b – границы интервала, a < b
// eps - точность решения
// Выход: x – решение уравнения f(x)=0
//----------------------------------------------
float BinSolve ( float a, float b, float eps )
{
float c;
while ( b - a > eps )
{
c = (a + b) / 2;
if ( f(a)*f(c) < 0 )
b = c;
else a = c;
}
return (a + b) / 2;
}

float f ( float x )
{
return x*x – 5;
}

Метод деления отрезка пополам//----------------------------------------------// BinSolve находит решение на [a,b]//     методом деления отрезка пополам

Слайд 9Как подсчитать число шагов?
float BinSolve ( float a, float b,


float

eps, int &n )
{
float c;
n = 0;
while ( b - a > eps )
{
c = (a + b) / 2;
if ( f(a)*f(c) < 0 )
b = c;
else a = c;
n ++;
}
return (a + b) / 2;
}

int &n

n = 0;

n ++;

значение переменной меняется внутри функции

Как подсчитать число шагов?float BinSolve ( float a, float b,

Слайд 10Метод итераций (повторений)
Задача:
Эквивалентные преобразования:
имеет те же решения при
Идея решения:
– начальное

приближение (например, с графика)
Проблемы:
как лучше выбрать ?
всегда ли

так можно найти решение?
Метод итераций (повторений)Задача:Эквивалентные преобразования:имеет те же решения приИдея решения:– начальное приближение (например, с графика)Проблемы:как лучше выбрать

Слайд 11Сходимость итераций
Сходящийся итерационный процесс: последовательность

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

сходимость
Сходимость итерацийСходящийся итерационный процесс: последовательность          приближается (сходится) к

Слайд 12Расходимость итераций
Расходящийся итерационный процесс: последовательность

неограниченно возрастает или убывает, не приближается

к решению.

односторонняя расходимость

двусторонняя расходимость

Расходимость итерацийРасходящийся итерационный процесс: последовательность          неограниченно возрастает или

Слайд 13От чего зависит сходимость?
сходится
расходится
Выводы:
сходимость итераций зависит от производной
итерации сходятся при

и расходятся

при
сходимость определяется выбором параметра b

От чего зависит сходимость?сходитсярасходитсяВыводы:сходимость итераций зависит от производнойитерации сходятся при

Слайд 14Как выбрать b?
наугад, пробовать разные варианты
для начального приближения x0






пересчитывать

на каждом шаге, например:

Как выбрать b?наугад, пробовать разные вариантыдля начального приближения x0 пересчитывать на каждом шаге, например:

Слайд 15Метод итераций (программа)
//----------------------------------------------
// Iter решение уравнения методом итераций
// Вход: x

– начальное приближение
// b - параметр
//

eps - точность решения
// Выход: решение уравнения f(x)=0
// n - число шагов
////----------------------------------------------
float Iter ( float x, float b, float eps, int &n)
{
float dx;
n = 0;
while ( 1 ) {
dx = b*f(x);
x = x + dx;
if ( fabs(dx) < eps ) break;
n ++;
if ( n > 100 ) break;
}
return x;
}

аварийный выход (итерации расходятся)

нормальный выход

Метод итераций (программа)//----------------------------------------------// Iter решение уравнения методом итераций// Вход: x – начальное приближение//    b

Слайд 16Метод Ньютона (метод касательных)

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

Слайд 17Метод Ньютона (программа)
//----------------------------------------------
// Newton решение уравнения методом Ньютона
// Вход: x

– начальное приближение
// eps - точность решения
//

Выход: решение уравнения f(x)=0
// n - число шагов
//----------------------------------------------
float Newton ( float x, float eps, int &n)
{
float dx;
n = 0;
while ( 1 ) {
dx = f(x) / df(x);
x = x - dx;
if ( fabs(dx) < eps ) break;
n ++;
if ( n > 100 ) break;
}
return x;
}

float f ( float x ) {
return 3*x*x*x+2*x+5;
}
float df ( float x ) {
return 9*x*x + 2;
}

Метод Ньютона (программа)//----------------------------------------------// Newton решение уравнения методом Ньютона// Вход: x – начальное приближение//    eps

Слайд 18Метод Ньютона
быстрая (квадратичная) сходимость – ошибка на k-ом шаге обратно

пропорциональна k2
не нужно знать интервал, только начальное приближение
применим для функция

нескольких переменных

нужно уметь вычислять производную (по формуле или численно)
производная не должна быть равна нулю

может зацикливаться

Метод Ньютонабыстрая (квадратичная) сходимость – ошибка на k-ом шаге обратно пропорциональна k2не нужно знать интервал, только начальное

Слайд 19Численные методы (язык Си)
Тема 2. Вычисление площади (интеграла)
© К.Ю. Поляков,

2008-2009

Численные методы (язык Си)Тема 2. Вычисление площади 		 (интеграла)© К.Ю. Поляков, 2008-2009

Слайд 20Площадь криволинейной трапеции

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

Слайд 21Метод (левых) прямоугольников
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
float Area()
{

float x, S = 0, h=0.001;
for ( x =

x1; x < x2; x += h)
S += h*(f1(x) – f2(x));
return S;
}

for ( x = x1; x < x2; x += h )
S += f1(x) – f2(x);
S *= h;

Метод (левых) прямоугольниковy = f1 (x)y = f2 (x)S1S2S3S4float Area(){ float x, S = 0, h=0.001; for

Слайд 22Метод (правых) прямоугольников
x
y
x2
x1
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
float Area()
{

float x, S = 0, h=0.001;
for ( x =

x1; x < x2; x += h)
S += h*(f1(x+h) – f2(x+h));

return S;
}

for ( x = x1; x < x2; x += h )
S += f1(x+h) – f2(x+h);
S *= h;

Метод (правых) прямоугольниковxyx2x1y = f1 (x)y = f2 (x)S1S2S3S4float Area(){ float x, S = 0, h=0.001; for

Слайд 23Метод (средних) прямоугольников
x
y
x2
x1
y = f1 (x)
y = f2 (x)
S1
S2
S3
S4
float Area()
{

float x, S = 0, h=0.001;
for ( x =

x1; x < x2; x += h)
S += h*(f1(x+h) – f2(x+h));

return S;
}

for ( x = x1; x < x2; x += h )
S += f1(x+h/2) – f2(x+h/2);
S *= h;

левые (правые):

средние

Метод (средних) прямоугольниковxyx2x1y = f1 (x)y = f2 (x)S1S2S3S4float Area(){ float x, S = 0, h=0.001; for

Слайд 24Метод трапеций
x
y
x2
x1
y = f1 (x)
y = f2 (x)
for ( x

= x1; x < x2; x += h )

S += f1(x) – f2(x) +
f1(x+h) – f2(x+h);
S *= h/2;

S =( f1(x1) - f2(x1)
+ f1(x2) - f2(x2) )/2.;
for ( x = x1+h; x < x2; x += h )
S += f1(x) – f2(x);
S *= h;

Метод трапецийxyx2x1y = f1 (x)y = f2 (x)for ( x = x1; x < x2; x +=

Слайд 25Метод Монте-Карло
Применение: вычисление площадей сложных фигур (трудно применить другие методы).
Требования:

необходимо уметь достаточно просто определять, попала ли точка (x, y)

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

Слайд 26Метод Монте-Карло
Вписываем сложную фигуру в другую фигуру, для которой легко

вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными

координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:

Всего N точек

На фигуре M точек

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

!

Метод Монте-КарлоВписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь (прямоугольник, круг, …). Равномерно N

Слайд 27Численные методы (язык Си)
Тема 3. Вычисление длины

кривой
© К.Ю. Поляков, 2008-2009

Численные методы (язык Си)Тема 3. Вычисление длины         кривой© К.Ю.

Слайд 28Длина кривой
Точное решение:
нужна формула для производной
сложно взять интеграл
Приближенное решение:

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

Слайд 29Длина кривой
//-----------------------------------------
// CurveLen вычисление длины кривой
// Вход: a, b –

границы интервала
// Выход: длина кривой y = f(x) на [a,b]
//-----------------------------------------
float

CurveLen ( float a, float b )
{
float x, dy, h = 0.0001,
h2 = h*h, L = 0;
for ( x = a; x < b; x += h ) {
dy = f(x+h) - f(x);
L += sqrt(h2 + dy*dy);
}
return L;
}
Длина кривой//-----------------------------------------// CurveLen вычисление длины кривой// Вход: a, b – границы интервала// Выход: длина кривой y =

Слайд 30Численные методы
Тема 4. Оптимизация
© К.Ю. Поляков, 2008-2009

Численные методыТема 4. Оптимизация© К.Ю. Поляков, 2008-2009

Слайд 31Найти x, при котором

или

при заданных ограничениях.

Основные понятия

Оптимизация – поиск оптимального (наилучшего в некотором смысле) решения.
Цель: определить значения неизвестных параметров, при которых заданная функция достигает минимума (затраты) или максимума (доходы).

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

или

Найти x, при котором           или

Слайд 32Локальные и глобальные минимумы
глобальный минимум
Задача: найти глобальный

минимум.
Реальность:
большинство известных алгоритмов находят только

локальный минимум вблизи начальной точки
алгоритмы поиска глобального минимума в общем случае неизвестны

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

Локальные и глобальные минимумыглобальный минимумЗадача: найти глобальный          минимум.Реальность:большинство

Слайд 33Минимум функции одной переменной
Дано: на интервале [a,b] функция непрерывна и

имеет единственный минимум.
Найти: x*
y = f (x)
Принцип сжатия интервала:

Минимум функции одной переменнойДано: на интервале [a,b] функция непрерывна и имеет единственный минимум.Найти: x*y = f (x)Принцип

Слайд 34Минимум функции одной переменной
Коэффициент сжатия:
Самое быстрое сжатие:
при
должно быть c 

d
Метод «почти половинного» деления:
– малое число
нужно искать два значения функции

на каждом шаге
Минимум функции одной переменнойКоэффициент сжатия:Самое быстрое сжатие:придолжно быть c  dМетод «почти половинного» деления:– малое числонужно искать

Слайд 35Отношение «золотого сечения»
Идея: выбрать c и d так, чтобы на

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

определения g:

Отношение «золотого сечения»:

Отношение «золотого сечения»Идея: выбрать c и d так, чтобы на каждом шаге вычислять только одно новое значение

Слайд 36Метод «золотого сечения»
//----------------------------------------------
// Gold поиск минимума функции («золотое сечение»)
// Вход:

a, b – границы интервала
// eps –

точность
// Выход: x, при котором f(x) имеет минимум // на интервале [a,b]
//----------------------------------------------
float Gold (float a, float b, float eps )
{
float x1, x2, g = 0.618034, R = g*(b - a);
while ( fabs(b-a) > eps ) {
x1 = b - R; x2 = a + R;
if ( f(x1) > f(x2) ) a = x1;
else b = x2;
R *= g;
}
return (a + b) /2.;
}
Метод «золотого сечения»//----------------------------------------------// Gold поиск минимума функции («золотое сечение»)// Вход: a, b – границы интервала//

Слайд 37Функции нескольких переменных
Проблемы:
нет универсальных алгоритмов поиска глобального минимума
неясно, как выбрать

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

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

Слайд 38Метод покоординатного спуска
Идея:
выбираем начальную точку
будем менять только x1, а остальные

переменные «заморозим», находим минимум по x1
теперь будем менять только x2,

а остальные переменные «заморозим», …

начальное приближение

минимум

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

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

Метод покоординатного спускаИдея:выбираем начальную точкубудем менять только x1, а остальные переменные «заморозим», находим минимум по x1теперь будем

Слайд 39Градиентные методы
Градиент – это вектор, показывающий направление

наискорейшего возрастания

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

минимум

начальное приближение

быстрая сходимость

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

градиент

Градиентные методыГрадиент – это вектор, показывающий направление

Слайд 40Метод случайного поиска
Идея:
выбираем начальную точку
пробуем сделать шаг в случайном направлении
если

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

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

очень большой объем вычислений

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

Слайд 41Конец фильма

Конец фильма

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика