Этапы решения задач на ЭВМ

Этапы решения задач на ЭВМ Этапы решения задач на ЭВМ 1 Общая формулировка физической задачи 2 Математическая формулировка задачи 3 Выбор математического метода решения задачи 4 Составление алгоритма решения 5 Составление и отладка программы 6 Тестирование программы 7 Решение задачи и представление результатов Погрешности и ошибки вычислений Причины – неустранимые погрешности – погрешность метода решения задачи – вычислительные погрешности из-за ошибок округления в процессе счета Вычислительные погрешности x=m10p где |m|<1 – мантисса; p – целое число – порядок. В компьютере 0,1|m|<1, т.е. число представлено в нормализованном виде 2.910-39…1.71038 1.510-45…3.41038 5.010-324…1.710308 3.410-4932…1.1104932 11-12 цифр 7-8 цифр 15-16 цифр 19-20 цифр 6 байт 4 байта 8 байт 10 байт Ошибок округления в процессе счета 0.2567  10  0.2567  10 4 0.0001236  10   точный результат 0.2568236  10 4 0.1236  101 4 4  0.2567  10 4 0.0001  10 4 на ЭВМ 0.2568  10 4 Ошибка вычисления 0.236  10 0 – абсолютная – x=x–x* – используется редко; – относительная – x=(x–x*)/|x*|. Вычисление функций   f ( x )   a ( n)  x . f ( x)   (1) n a(n)  x n . n n 0 n 0 N f ( x )   a ( n) x n n 0 f ( x) a( N ) x N N 1 n a ( n ) x   . a( N ) x N  a( N  1) x N 1  . N 1 n a ( n ) x  n 0 n 0 f 1 ( x)  f 2 ( x)  , f 2 ( x)  . Операторы цикла Рекуррентный метод an+1=anbn, f =f+ a( i ) x F i abs(a (i )x /f)> i xn f ( x)   . n 1 n  n!  T i = i +1 F abs(a (i )xi /f)> xn+1=(xn)x. f =f+ a( i ) xi T i = i +1 an =xn/(nn!) n 1 an 1 x n 1  (n  1)  (n  1)! an 1 x n  n! xn bn    , n an (n  1)(n  1) (n  1)  (n  1)! x x, E Пример n =1 a =x  n x f ( x)   . n 1 n  n! f =a n = n +1 xn bn  (n  1)(n  1) b = x· (n-1)/n 2 a= a· b f= f+a a n 1 xn  an . 2 (n  1) F x, E, f, n a f  E T #include stdaf.h int _tmain() { int n; float x,E,a,f; scanf(%f %f,&x,&E); n=1; x=a; f=a; do { n=n+1; b=x(n-1)/n2; a=ab; f=f+a; }while(abs(a/f)>E); printf(%f %f %f %i,x,E,f,n); return 0; } Задания на тему вычисления функций 1 Неполная гамма-функция ( z )  ( a, z )  z  ; a  0. n0 n!(a  n) a  2 Интегральная показательная функция xn Ei( x)  0.57721566  ln( x)   ; x  0. n1 n  n! 3 Интегральный синус  (1) n z 2 n1 Si( z )   . n0 (2n  1)(2n  1)!  n Задания на тему вычисления функций 4 Интеграл вероятности: 2  (1) n z 2 n1 erf ( z )  .   n0 n!(2n  1) 5 Косинус-интеграл Френеля 2 z  (1) k z 2 k C ( z)  .   k 0 (2k )!(4k  1) 6 Функция Бесселя z    z 4 . J ( z)     n n 2  k 0 2 k k!(n  k )! Задания на тему вычисления функций 7 Гипергеометрический ряд  (a) n (b) n n F (a, b, c, z )    z ; ( z  1, c  0), n 0 (c) n n! где (x)n – символ Похгаммера, (x)n=(x(x+1) (x+2)…(x+n–1). 8 Многочлен Лагерра m x Ln ( x)  (n!)  (1) . 2 (m!) (n  m)! m0 2 n m Численное интегрирование b S   f ( x)dx a f( x) Методы численного интегрирования: – численное интегрирование для равноотстоящих узлов, a b b  f ( x)dx  F (b)  F (a), a x – численное интегрирование неравноотстоящих узлов. для Численное интегрирование для равноотстоящих узлов Метод Ньютона-Котеса  x0  nx где   y ( x)dx  a0 y0  a1 y1    an yn , x0  nk n (  1 ) (  1)(  2)    (  n) a k  d.   k!(n  k )! 0 k x0  Nx x0  nx x0 2 nx x0  Nx x0 x0 x0 nx x0 ( N 1) x  y( x)dx   y( x)dx   y( x)dx     y( x)dx Метод Ньютона-Котеса 1) n=0 – метод прямоугольников a0=1 x0  Nx N 1 x0 m 0  y( x)dx  x  y( xm ), xm=x0+mx 2) n=1 – метод трапеций a0=1/2, a1=1/2 (x0, x0+x); (x0+x, x0+2x);… (x0+(N–1)x, x0+Nx)   x  y ( x)dx  2 y ( x0 )  y ( x1 )  y ( x1 )  y ( x2 )  y ( x2 )  y ( x3 )    y ( xN 1 )  y ( xN )  x0 x0  Nx N 1 x  .  y ( x )  2 y ( x )  y ( x )  m N   2  m 1  Метод Ньютона-Котеса 3) n=2 – метод (формула) Симпсона a0=1/6, a1=2/3, a2=1/6 (x0,x0+x,x0+2x); (,x0+2x,x0+3x,x0+4x);… (x0+(N–2)x,x0+(N–1)x,x0+Nx) x  y( x)dx  3  y( x0 )  4 y ( x1 )  y ( x2 )  y( x2 )  4 y( x3 )  y( x4 )  y ( x4 )  4 y( x5 )  y( x6 )    x0 x0  Nx   N 1 N 1 x   y ( x0 )  4  y ( xm )  2  y ( xm )  y ( xN ).  3  m1 m2 нечетн четн   Коэффициенты Котеса n ak a0 2 3 4 5 6 0,5 0,1667 0,375 0,3111165 0,329869 0,292861 0,5 0,6667 0,125 1,422201 1,3020585 1,542839 a2 0,1667 0,125 0,533366 0,8680721 0,193860 a3 0,375 1,422201 0,8680721 1,942804 0,3111165 1,3020585 0,193860 a1 a4 a5 a6 1 1 0,329869 1,542839 0,292861 Численное интегрирование для неравноотстоящих узлов b  y( x)dx a ba ba x z 2 2 ba f ( z)  y( x). 2 1  f ( z )dz, 1 Метод Гаусса 1 n 1 k 1  f ( z )dz   ak f ( z k ), ak  2 (1  z )Pn ( z k ) 2 2 k ; n 2  n=1,2,3,…; zk – корни многочлена Лежандра (2n  2m)! Pn ( z )  2  (1) z n2 m . m!(n  m)!(n  2m)! m 0 n m Метод Гаусса n zk 2 0,57735 ak 1 n 4 zk ak 0,339981 0,652145 0,861136 0,347855 3 8/9 0,774597 5/9 5 0,568889 0,538469 0,478629 0,906180 0,236927 Метод Чебышева n=2 n=3 2 n  f ( z )dz  n  f ( z k ), k 1 1 0,577350 0,707107 0,794654 0,187592 0,832497 0,374541 z1,2 z2 z1,3 z1,4 z2,3 z3 z1,5 z2,4 n=4 n=5  Лаггера для 1 x  e y ( x)dx;  Эрмита для e   x2 y ( x)dx; Задания на тему «Численное интегрирование» 2  x( x  0,3)( x  0,6)( x  1)( x  1,5)( x  1,8)( x  2)  0,05dx  0,1025875803 1 Метод Ньютона-Котеса n=3 6 Метод Гаусса n=4 2 Метод Ньютона-Котеса n=4 7 Метод Гаусса n=5 3 Метод Ньютона-Котеса n=5 8 Метод Чебышева n=3 4 Метод Ньютона-Котеса n=6 9 Метод Чебышева n=4 5 Метод Гаусса n=3 10 Метод Чебышева n=5 Интерполяция функций f( x) y n1  y n f ( x)  y n  ( x  xn ) xn1  xn f1 f2 x1 x2 x3 x4 x xN-1 xN x Метод Лагранжа ( x  x1 )( x  x2 )    ( x  xn ) f ( x)  f ( x0 )  ( x0  x1 )( x0  x2 )    ( x0  xn ) ( x  x0 )( x  x2 )    ( x  xn )  f ( x1 )  ( x1  x0 )( x1  x2 )    ( x1  xn )    ( x  x0 )( x  x1 )    ( x  xn 1 )  f ( xn ) . ( xn  x0 )( xn  x1 )    ( xn  xn 1 ) Метод Ньютона f ( x)  f ( x0 )  ( x  x0 )1 ( x0 , x1 )  ( x  x0 )( x  x1 ) 2 ( x0 , x1 , x2 )   n 1    ( x  x k ) n ( x0 , x1 , x2 ,, xn ), k 0 f ( x1 )  f ( x0 ) 1 ( x0 , x1 )  ; ( x1  x0 )  n1 ( x1 , x2 , xn )   n1 ( x0 , x1 , xn1 )  n ( x0 , x1 , x2 , xn )  . ( x n  x0 ) Интерполяция с оптимальным выбором узлов Многочлен y(x) степени n, который совпадает с f(x) в n+1 точках, x=xi (i=0,1,2,…,n) на отрезке [a, b] при условии минимального значения максимального уклонения n   min max  ( x  xi  a  x b  i 0  строится на основе многочленов Чебышева: Интерполяция с оптимальным выбором узлов на основе многочленов Чебышева n 1  2x  b  a  y ( x)  A0   Ak Tk  , 2 k 1  ba  2 n  (2i  1)    Ak  ;  y ( xi ) cos n  1 i 0  2n  1  Tk(z)=cos(karcos(z)) ba ba  (2i  1)  xi   cos ; 2 2  2n  2  i=1,2,…,n. Интерполяция y(x) f( x) f( x) По Чебышеву Истинная f(x) x1 x2 x3 x4 xN-1 xN x x1 x2 x3 x4 xN-1 xN x Как оценить ошибку при замене f(x) на y(x) на интервале (a,b)? Среднеквадратическая ошибка Минимизация b 1 2 2  f ( x)  y( x)  dx.    ba a b 1 6 6  f ( x)  y( x)  dx    ba a b 1    f ( x)  y( x)  dx    ba a Аппроксимация функций Интерполяция y(x) f( x) Истинная f(x) F(x)=a00(x)+a11(x)+…+ ann(x) Результат аппроксимации Условие ортогональности функции b   x  i ( x) j ( x)dx  0 или x1 x2 x3 x4 xN-1 xN x a m   x  i ( x k ) j ( x k )dx  0 k 0 m     k F ( xk )  f ( xk ) , 2 k 0 2 при ij. m ai    k f ( x k ) i ( x k ) k 0 m   k  ( xk ) k 0 2 i ; i=0,1,2,…,n; nm. Аппроксимация на равноотстоящих точках Если m+1=2M+1 точек делят отрезок [a,b] на 2M равных частей, ba xk   kx; 2 ba x  ; 2M  2x  b  a   i ( x)  Pi  M ,2M ,  ba  Pi t ,2M    (1) i  n i n 0 k=1, 2,…, M i=0,1,2,…,2M (i  n) 2 n  ( M  t ) n  ; 2 n  (n!) (2M ) z[0]=1, z0; 0[n]=0, n=1,2,…; z[n]=z(z-1)(z-2)…(z–n+1), n=1,2,… 2М аппроксимация P0(t,2M)=1 t P1 t ,2M   ; M 3t  M ( M  1) P2 t ,2M   ; M (2M  1) 5t 3  (3M 2  3M  1)t P3 t ,2M   ; M ( M  1)(2M  1) 2 35t 4  5(6M 2  6M  5)t 2  3M ( M 2  1)(M  2) P4 t ,2M   ; 2M ( M  1)(2M  1)(2M  3) 63t 5  35(2M 2  2M  3)t 3  (15M 4  30M 3  35M 2  50M  12)t P5 t ,2M   . 2M ( M  1)(2M  1)(2M  3)(M  2) Тригонометрическая аппроксимация Даны m значений функции y(xk)=yk при t xk  k ; m n  1  2x   2x   Yk  A0    Ai cos i   Bi sin  i  ; 2 i 1   T   T  2 m 1  2k  Ai   y k cos i , m ik 0  m  k=0,1,2,…m–1. n= T Метод простой итерации Уравнение f(x)=0 приводится к виду x=g(x) и далее, зная начальное значение корня x0, вычисляется следующее приближенное значение x1=g(x0) и т.д.: xn+1=g(xn) до тех пор, пока |xn–xn+1|<, но если значение корня велико, то лучше использовать относительную точность xn  xn 1  . xn 1 Метод очень прост, но не всегда сходится к решению. Условие сходимости метода простой итерации Сходится y=x y(x) g(x2) g(x1) g(x0) y=g(x) x0 x x1 x2 x3 y(x) Расходится y=x g(x3) g(x1) g(x0) g(x2) y(x) Сходится y=x g(x0) g(x2) y=g(x) g(x3) g(x1) x x0 x2 x3 x1 y(x) Расходится y=g(x) g(x1) g(x0) y=x y=g(x) x3 x1 x0 x2 x x0 x1 x2 x dg ( x)  1. dx Метод Ньютона Смысл этой формулы заключается в линеаризации функции f(x) в исходной точке xn. В точке xn функция f(x) заменяется прямой линией, проходящей через точку xn с наклоном 1 f ( x n ) . Далее находят точку пересечения этой линии с осью x, т.е. определяют xn+1 xn1 f ( xn )  xn  , f ( xn ) f( x) f( x) при f (xn)0. x3 x2 x1 x0 x x1 Если функция задана аналитически, то можно вычислить f (x). Если это трудно, то численно f (x)= (f(x+x)–f(x)/ x. x0 x Метод секущих xn1 xn  xn1  xn  f ( xn ). f ( xn )  f ( xn1 ) Метод хорошо применять, если сложно вычислить производную f(x) f( x) f( x) x2 x4 x4 x3 x2 x1 x0 x x1 x3 x0 x Модифицированный метод Ньютона f ( x n ) 1 [ f ( x n )] f ( x n )  xn   . 3 f ( x n ) 2 [ f ( x n )] 2 x n 1 Метод Эйткена-Стеффенсона f(x)=0 приводится к виду x=g(x) x1=g(x0); x4=g(x3); x2=g(x1); x5=g(x4); ( x1  x0 ) 2 x3  ; x2  2 x1  x0 ( x 4  x3 ) 2 x6  x5  2 x 4  x3 Задание на тему «Решение уравнений» Решить уравнение x2+2x-3=0 (для проверки x1= -3; x2=1) 1 Методом деления отрезка пополам. 2 Методом простой итерации. 3 Методом Ньютона. 4 Методом секущих 5 Методом Эйткена-Стеффенсона Оптимизация (нахождение экстремума) min F ( x )  max F ( x ) F(x1,x2,…,xn) x =(x1,x2,…,xn) F(x) F ( x )  min ( x )  0; 1 ( x )  0 Локальные Глобальный , ,, x0 x0 ,,, x0 x Метод деления отрезка F(x) F(b) F(a) F( a1) находится на отрезке (a1, b); если F(a1)F(b1), то экстремум b1 b x находится на отрезке (a1, b1); a, b,  Fa=f(a) Fb=f(b) dx=(b- a)/2 Алгоритм метод деления отрезка a1=a+dx b1=b- dx Fa1=f(a1) Fb1=f(b1) F T Fa 1=Fb 1 a= a1 F T Fa1 a,Fa Метод перебора (прямой перебор) Целевая функция – n переменных F (x ) Область допустимых значений x  (a , b ). По каждой переменной – сетка из m-значений Найдем min F ( x ) и координату x( a ,b ) a  (a0 , a1 , , am ) b  (b0 , b1 ,  , bm ) x0 Недостаток – огромное (mn) количество вычислений функции F (x ) Метод покоординатного перебора Вместо min F ( x ) x( a ,b ) ищется последовательно минимум по каждой координате min min  min F ( x ) x1 ( a1 ,b1 ) x2 ( a2 ,b2 ) xт ( aт ,bт ) Количество операций вычисления F (x ) – mn раз (mn<