1. Погрешность результата численного решения задачи. Источники погрешности. Абсолютная и относительная погрешность.

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

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

Например, числа 34,537, 0,00362 и 7,002 имеют пять, три и четыре значащих цифры соответственно. 

Точные числа А могут иметь цифр больше, чем это необходимо. В этих случаях точные числа заменяют приближенными, пользуясь пра­вилом их округления. Округлить число до заданного разряда или до требуемого количе­ства значащих цифр означает сохранить требуемое количество цифр (отсчитывается слева) при отбрасывании остальных.

Например, 6,426281 = 6,43 означает округление до сотых или до трех значащих цифр. 

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

Разность между точным значением числа А и его приближенным значением  называют погрешностью приближенного числа  , т.е. 

     (1.1)

Как видно из (1.1), погрешность может быть положительной, отрицательной или равной нулю. Абсолютное значение погрешности числа    называют абсолютной погрешностью:

    (1.2)

Поскольку точное значение числа А обычно неизвестно, то неиз­вестна и абсолютная погрешность . Поэтому на практике рассматри­вают предельную (граничную) абсолютную погрешность приближен­ного числа , которая равняется или превышает максимальное значе­ние разности между числом  и его точным значением, т.е.

       (1.3)

 Заметим, что  всегда положительна.

Абсолютная погрешность  позволяет установить границы, в кото­рых располагается точное число А, поскольку из (1.2) имеем

                                          (1.4)

 

2. Методы решения конечных уравнений

Пусть имеем уравнение

f(x) =  0                                                                     (1.20)

на заданном сегменте [а, b]. Предположим также, что функция f(x) кусочно-непрерывна и имеет кусочно-непрерывную производную.

Функцию (4.20) называют алгебраическим уравнением n-й степени, если f(х) можно представить соответствующим полиномом, т.е.

         (1.21)

Если же в f(x) входят элементарные (тригонометрические, показательные, логарифмические и т.п.) функции, то имеем трансцендентное уравнение.

Алгебраические и трансцендентные уравнения обобщают термином "конечные" уравнения.

Всякое значение х = £, обращающее функцию (1.20) в нуль, т.е. такое, что f(£) = 0, называют корнем уравнения f(x) = 0. Способ определения указанного корня именуют решением уравнения. Некоторые из корней уравнения (1.20) могут совпадать (повторяться). В этом случае имеют кратные корни. При k совпадающих корнях имеют корень k-й кратности. Если k = 1, то имеют простой корень. Число £ является корнем k-й кратности, если при x: = £ обращаются в нуль как функция f(£), так и все ее производные до (k-1)-го порядка включительно:

    (1.22)

 Численное решение конечных уравнений (приближенное определение значений корней) удобно проводить по следующей методике. Сначала выявляют достаточно малые промежутки для каждого из корней (простого или кратного) уравнения, т.е. выполняют процедуру отделения корней. Затем находят в этих промежутках значения корней с заданной точностью, обеспечивая тем самым уточнение корней. Отделение корней можно проводить графически и аналитически.

При графическом способе исходное уравнение (1.20) представляют в форме

f₁(x) = f₂(x)                                 (1.23)

получая два графика:

у₁ =f₁(х)  и  у₂ =f₂(х).               (1.24)

Поскольку для корней уравнения (1.20)

 f(x)= f₁(х)- f₂(х)=0                (1.25)

то их численные значения получают по абсциссам точек пересечения этих графиков. В частном случае при f₂(х) = 0 график функции у₂ = f₂(х)=0 совпадает с осью абсцисс и тогда искомые корни конечного уравнения (1.20) получают по точкам пересечения графика f(х) = f₁(х) с этой осью.

Аналитические методы отделения корней конечных уравнений используют различные способы упрощенного аналитического решения задачи. Наибольший практический интерес имеют две следующие разновидности. В первой осуществляется переход от искомого к более простому уравнению, имеющему приблизительно те же самые значения корней. Зачастую это достигается исключением из исходного уравнения членов с малыми значениями коэффициентов. Вторая разновидность основана на непосредственном применении свойств непрерывных функций (известных теорем) для конкретизации различных вспомога­тельных процедур: определения числа корней для алгебраических уравнений, анализа промежутков с корнями, косвенного нахождения некоторых корней и т.п.

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

a_k < £_k <b_k           (1.26)

где a_k и b_k — начало и конец интервала, в котором располагается k-й корень £_k функции f(x).

Тогда в качестве первого приближенного значения для k-го корня можно принять, например, центр интервала

 £_k1=(a_k+b_k)/2,       (1.27)

В этом случае для абсолютной погрешности 8и (см. разд. 4.3) имеем

e_k1<(b_k -a_k )/2     (1.28)

При необходимости получить более высокую точность удобно применять итерационные методы, заключающиеся в следующем. Подставляют приближенное значение k-го корня (1.27) в исходное уравнение (1.20) и, принимая f(£_k1) = b_k1 или f(£_k1) = a_k1, находят второе значение этого корня в более узком интервале

a_k < £_k2 <b_k1           (1.29)

 или

a_k1 < £_k2 <b_k             (1.30) 

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

3. Метод половинного деления

Если вид исходной функции f(х) достаточно сложный, то вычисление f'(x) в методе касательных  может заметно усложнить алгоритм 1.2.

Для решения таких уравнений на ЭВМ особенно удобен метод половинного деления. В этом методе также требуется, чтобы ординаты анализируемой функции f(x) =0  имели на границах сегмента [х_A, х_B] разные знаки (рис. 1.7),

т.е.

f(х_A)*f(х_B)<0                                                              (1.45)

Для нахождения корня, принадлежащего промежутку

 (х_B1-х_A). делим его пополам, исследуя исходную функцию в средней точке х=х_B1  . Здесь возможны следующие случаи:

совпадение значения корня х = x с абсциссой точки х_B1  , т.е.

откуда искомый корень

                                                                      (1.46)

 несовпадение х=x, с точкой x_B1 (см. рис. 1.7), т.е.

                                                                 (1.47)

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

На рис. 1.7 этому условию удовлетворяет промежуток

(х_B1-х_A)

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

 d_n(n=0,1,2,...), для которых можно записать,

,       (1.48)

где n — номер цикла; d₀ =(х_B - х_A)— исходный промежуток (см. рис. 1.7).

В пределе при

 соотношение (1.48) имеет общий предел, совпадающий со значением корня х = x. Тогда абсолютная точность расчета корня методом половинного деления

.          (1.49)

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

4.  Метод хорд

Сущность метода также основана на последовательном приближе­нии к искомому корню конечного уравнения

f(х) = 0. Однако в отличие от метода касательных здесь на каждом шаге итерационного процесса участок истинной кривой у =f(x) заменяют соответствующей хордой.

Расчетная формула.

На рис. 1.6 показан график функции у =f(x) вблизи корня x, которому соответствует точка пересечения дуги ВА с осью абсцисс.

Задавая два значения х_A и х_B, которым соответствуют разные знаки фунции f(x), например:

f(x_A)>0    и       f(x_B)<0,                                                  (1.37)

соединяют эти точки хордой ВА.

Уравнение прямой ВА можно записать

                                (1.38)

При y₁ = 0   получаем значение точки пересечения х₁ этой прямой (хорды) с осью абсцисс, т.е.

                                        (1.39)

Откуда после несложных преобразований получают

                                      (1.40)

Выявив знак функции f(x₁) в найденной точке х₁ (см. рис. 1.6), заменяют соответствующее по знаку значенение х_A  или х_B в (1.41) новой более точной величиной х₁. Так, например, для случая, анализируемого на рис. 1.6, в (1.40) требуется заменить х_A значением х₁, получая уже для хорды BА₁ второе приближение корня

                                      (1.41)

Продолжая эту процедуру, получают для (n+1)-го приближения

                                      (1.41)

 Как видно из рис. 1.6, сходящаяся последовательность значений x_k (k = 1, 2, ..., n+1) обеспечивает получение корня x_k =x с любой точностью.

Практические рекомендации.

При разработке машинных алгоритмов расчетное соотношение (1.42) преобразуют к более удобному для итерационных формул виду, т.е.

                                           (1.43)

где x₀ и x₁ - исходные значения абсцисс функции f(х), например x_A и x_B на рис. 4.6.

В этом случае условие сходимости решения можно записать

f(x₀)* f(x₁) <0                                             (1.44)

 

5. Метод касательных

 

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

При выделении интервала (а, b), в котором ищется действительный корень уравнения,

 исходят из следующего предположения. Если на границах некоторого интервала непрерывная функция f(х) принимает значения разных знаков, то в этом интервале уравнение f(х) = 0 имеет хотя бы один корень.

Сущность метода заключается в последовательном приближении к искомому корню конечного уравнения f(х) = 0  за счет взаимосвязанного смещения соответствующих касательных. Для уяснения метода на рис. 1.4 показан график функции y=f(x), пересекающей ось Ох в точке С, абсцисса которой х = x является корнем уравнения f(х) = 0.

  Расчетная формула.

Пусть АВ (см. рис. 1.4) - дуга кривой у =f(х) вблизи корня и обращена выпуклостью к оси Ох. Проведем через точку В с координатами (х_в, у_в) касательную к кривой. В этом случае угловой коэффициент касательной будет равняться производной от функции f(х) в точке касания В:

K=f’(x_B ).                                                             (1.31)

Тогда уравнение этой касательной, т.е. прямой Bx₁ , можно записать как

y - y_B =( x - x_B) f’(x)

При у = 0 и  у_B = f(x_B ) имеем (см. рис. 1.4)

- f(x_B ) = (x₁ - x_B )f’(x_B )                                                           (1.32)

где х₁ — абсцисса точки пересечения касательной с осью.

 Полагая x_B = х₀ и решая (1.32) относительно х₁, получаем первое приближение для корня

x₁ = x₀ - f(x₀ )/ f’(x₀ )

Абсциссе x₁ будет соответствовать новое значение функции у₁=f(x₁), определяемое координатами точки В₁. Проводя касательную из точки В₁ и повторяя многократно описанную процедуру, получаем итерационную формулу Ньютона

x_n+1 = x_n - f(x_n )/ f’(x_n )                                        (1.33)

Она позволяет шаг за шагом находить более точные значения простых корней алгебраических или трансцендентных уравнений f(x) = 0. При этом величины x₀, x_t x₂,... образуют сходящуюся к искомому корню х =x  последовательность (см. рис. 1.4).

Практические рекомендации.

Заметим, что при использовании формулы Ньютона может иметь место недопустимый процесс расхождения решения. Например, на рис. 1.5 представлен график функции у =f(x), обращенной к оси Ох вогнутостью.

Пусть по аналогии с предыдущим случаем (см. рис. 1.4) здесь также исходной является точка В. Нетрудно заметить, что касательная Вх₁’ не может обеспечить решения задачи. В то же время, если выбрать за исходную точку А, получим сходящуюся последовательность значений x_A, х₁, х₂,….

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

f(x₀ )* f’’(x₀ ) > 0                                                       (1.34)

где  f’’(x₀ )  - вторая производная анализируемой функции в выбранной исходной точке х₀.

Таким образом, простой корень алгебраических или трансцендентныx уравнений f(x ) = 0 можно вычислить по формуле Ньютона (1.33) с любой сколь угодной точностью, если нулевое приближение х₀ взято настолько близко к корню х =x  , что в интервале (x, х₀  ):

а) наклон кривой у =f(x) не равняется нулю.т.е.

:

б) кривая у =f(x) не имеет точек перегиба, т.е.

.

Для расчета корней с точностью до e итерационный процесс следует прекратить при выполнении условия

 ,                                             (1.35)

 где a - наименьшее значение f'(x) на сегменте [x_A,x_B]; b - наибольшее значение |f"(x)| на этом же сегменте. Условию (1.35) будет отвечать неравенство

 

.                                                     (1.36)

 

По формуле Ньютона можно находить и кратные корни, если использовать (4.36), но уже для производной от функции f(x), т.е. в общем случае

,

•где k=1, 2,... - порядок кратности корня для уравнения (1.20).

 

6. Метод простой итерации для решения конечных уравнений

 

Пусть имеем уравнение

f(x) =  0                    (1.20)

на заданном сегменте [а, b]. Предположим также, что функция f(x) кусочно-непрерывна и имеет кусочно-непрерывную производную.

Функцию (4.20) называют алгебраическим уравнением n-й степени, если f(х) можно представить соответствующим полиномом, т.е.

        (1.21)

Если же в f(x) входят элементарные (тригонометрические, показательные, логарифмические и т.п.) функции, то имеем трансцендентное уравнение.

Алгебраические и трансцендентные уравнения обобщают термином "конечные" уравнения.

Всякое значение х = £, обращающее функцию (1.20) в нуль, т.е. такое, что f(£) = 0, называют корнем уравнения f(x) = 0. Способ определения указанного корня именуют решением уравнения. Некоторые из корней уравнения (1.20) могут совпадать (повторяться). В этом случае имеют кратные корни. При k совпадающих корнях имеют корень k-й кратности. Если k = 1, то имеют простой корень. Число £ является корнем k-й кратности, если при x: = £ обращаются в нуль как функция f(£), так и все ее производные до (k-1)-го порядка включительно:

    (1.22)

Численное решение конечных уравнений (приближенное определение значений корней) удобно проводить по следующей методике. Сначала выявляют достаточно малые промежутки для каждого из корней (простого или кратного) уравнения, т.е. выполняют процедуру отделения корней. Затем находят в этих промежутках значения корней с заданной точностью, обеспечивая тем самым уточнение корней. Отделение корней можно проводить графически и аналитически.

При графическом способе исходное уравнение (1.20) представляют в форме

получая два графика:

у₁ =f₁(х)  и  у₂ =f₂(х).                (1.24)

Поскольку для корней уравнения (1.20)

f(x)= f₁(х)- f₂(х)=0                  (1.25)

то их численные значения получают по абсциссам точек пересечения этих графиков. В частном случае при f₂(х) = 0 график функции у₂ = f₂(х)=0 совпадает с осью абсцисс и тогда искомые корни конечного уравнения (1.20) получают по точкам пересечения графика f(х) = f₁(х) с этой осью.

Аналитические методы отделения корней конечных уравнений используют различные способы упрощенного аналитического решения задачи. Наибольший практический интерес имеют две следующие разновидности. В первой осуществляется переход от искомого к более простому уравнению, имеющему приблизительно те же самые значения корней. Зачастую это достигается исключением из исходного уравнения членов с малыми значениями коэффициентов. Вторая разновидность основана на непосредственном применении свойств непрерывных функций (известных теорем) для конкретизации различных вспомога­тельных процедур: определения числа корней для алгебраических уравнений, анализа промежутков с корнями, косвенного нахождения некоторых корней и т.п.

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

a_k < £_k <b_k                         (1.26)

где a_k и b_k — начало и конец интервала, в котором располагается k-й корень £_k функции f(x).

Тогда в качестве первого приближенного значения для k-го корня можно принять, например, центр интервала

 

£_k1=(a_k+b_k)/2,             (1.27)

В этом случае для абсолютной погрешности 8и (см. разд. 4.3) имеем

e_k1<(b_k -a_k )/2         (1.28)

При необходимости получить более высокую точность удобно применять итерационные методы, заключающиеся в следующем. Подставляют приближенное значение k-го корня (1.27) в исходное уравнение (1.20) и, принимая f(£_k1) = b_k1 или f(£_k1) = a_k1, находят второе значение этого корня в более узком интервале

a_k < £_k2 <b_k1                    (1.29)

или

a_k1 < £_k2 <b_k                   (1.30)

 

8. Общая формулировка задачи приближения функций

Введем понятие обобщенного многочлена:

               (2.7)

где f_k(х), k = 0, 1, 2, ..., m - система непрерывно дифференцируемых функций; c_k, k = 0,1,..., т — постоянные коэффициенты.

Задача о приближении формулируется следующим образом: данную функцию f(x) требуется приближенно заменить (аппроксимировать) обобщенным полиномом Q(x) так, чтобы отклонение f(x) от Q(x) на заданном множестве Х = {х} было наименьшим. Это можно достичь надлежащим подбором коэффициентов (2.7). Тогда многочлен Q(x) называют аппроксимирующим.

Если множество Х состоит из отдельных точек, то имеют точечное приближение, если же Х является отрезком

a £ х £b, то получают интегральное приближение.

На практике используют систему функций {f_k(х)} с целыми неотрицательными степенями переменной х, т.е.

тогда функция Q(x) отображается обычным многочленом:

.       (2.8)

 

9. Интерполяционная формула Лагранжа.

Полагая т= п, можно найти коэффициенты

а_i , i = 0, 1, 2, ..., п  интерполяционного многочлена Q(x) системы уравнений

а₀ + а₁ х₀ + а₂ х₀ ²+...+ а_i х₀ ⁿ=у₀ ,

а₀ + а₁ х₁ + а₂ х₁ ²+...+ а_i х₁ ⁿ=у₁ ,             (2.10)

…………………………………..

а₀ + а₁ х_n + а₂ х_n ²+...+ а_i х_n ⁿ=у₀ , 

которая имеет единственное решение. Заметим, что в правой части система (2.10) имеет значения заданной функции f(x) в узлах интерполяции, т.е. у_i = f(x).

Многочлен Q(x) = L_n(x), коэффициенты которого находят из решения (2.10), называют интерполяционной формулой Лагранжа:

           (2.11)

 

Раскрывая p_i(x), имеем

    (2.12)

Если функция f(x), подлежащая интерполяции, достаточное число раз дифференцируема, то погрешность интерполяции можно рассчитать по формуле

                        (2.13)

где x, - некоторое число в интервале интерполяции и зависящее от x.

 

10. Численное интегрирование Формула Ньютона-Котеса

Формулы Ньютона-Котеса.

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

1. Выбираем шаг h = (b - а)/п и разбиваем сегмент [а, b] на п равных частей посредством равноотстоящих точек

x₀=a,  x_i=x₀+ih,  i=1,2….,(n-1),  x_n=b,

y_i=f(x_i),  i=0,1,2,….,n

2. Заменяем функцию у соответствующим интерполяционным многочленом L_n(x) Лагранжа (см. разд. 2.3) и получаем

                                              (2.38)

где А_i, - некоторые коэффициенты.

3. Обращаясь к (2.11), с учетом обозначений

q=(x-x₀)/h,q^[n+1]=q(q-1)...(q-n)                     (2.39)

Интерполяционный многочлен Лагранжа можно записать

                  (2.40)

 

4. Подставив полученное значение L_n(x) в (2.38) вместо у и выполнив замену переменных в интеграле, имеем

                 (2.41)

i=0,1,2,…,n

 

5. Поскольку h = (b - a)/n,

то

A_i=(b-a)H_i.

Тогда для коэффициентов Котеса H_i, получаем

                  (2.42)

i=0,1,2,…,n

 

6. Формулу Ньютона-Котеса можно в этом случае представить так:

                              (2.43)

где

у_i =f_i(а + ih),  i = 0, 1, 2, ..., п,  h = (b - a)/n.