Презентация на тему Численые методы язык программирования СИ

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

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

сложно.

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

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


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

решения

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

сдвинуть правую границу интервала b = c;
Если f(c)*f(a)≥ 0, сдвинуть левую границу интервала a = c;
Повторять шаги 1-3, пока не будет b – a ≤ .

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

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

[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;
}

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 ++;

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

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

?
всегда ли так можно найти решение?

приближается (сходится) к

точному решению.

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

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

неограниченно возрастает или

убывает, не приближается к решению.

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

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

сходятся при

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

x0






пересчитывать на каждом шаге, например:

Вход: 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;
}

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

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

Вход: 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;
}

шаге обратно пропорциональна k2
не нужно знать интервал, только начальное

приближение
применим для функция нескольких переменных

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

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

(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;

(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;

(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;

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

средние

( 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;

другие методы).
Требования: необходимо уметь достаточно просто определять, попала ли

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