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

Погрешность математической модели.

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

2. Погрешность исходных данных.
Зависит от точности измерения параметров, используемых в модели. Любые измерения приближенны, поэтому и этот источник всегда влияет на решение.

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

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

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

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

Есть случайные и систематические источники погрешности округления.

Случайные источники обычно компенсируют друг друга.

Например:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Знаки Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru случайны и компенсируют друг друга при большом n.

Систематические источники вызывают накопление погрешности округления. Они являются дефектом структуры вычислений (алгоритма).

В машинной арифметике законы коммутативности (переместительный) и дистрибутивности (распределительный) не всегда соблюдаются.

Рекомендации для снижения ошибок округления:

  1. При сложении и вычитании последовательности чисел действия необходимо начинать с наименьших по абсолютной величине значений.
  2. Следует избегать вычитания двух близких чисел, преобразуя выражения.
  3. Количество арифметических действий для решения задачи нужно сводить к минимуму.
  4. Для уменьшения ошибки округления расчеты следует проводить с повышенной разрядностью (doubleprecisionв Pascal).

При выборе численного метода решения задачи необходимо учитывать следующее:

1. Погрешность метода должна быть на порядок меньше неустранимой погрешности. Увеличение погрешности метода снижает точность, уменьшение – увеличивает время решения задачи.

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

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

1. Решить задачу различными численными методами и результаты сравнить.

2. Незначительно изменить исходные данные и повторно решить задачу. Результаты сравнить. Если они различаются сильно, задача или метод ее решения являются неустойчивым – выбрать другой.

3.)Пусть в результате решения задачи по исходному значению величины x находится значение искомой величины y. Если исходная величина имеет абсолютную погрешность Dx, то решение имеет погрешность Dy. Задача называется устойчивой по исходному параметру x, если решение y непрерывно от него зависит, т. е. малое приращение исходной величины Dx приводит к малому приращению искомой величины Dy. (малые погрешности в исходной величине приводят к малым погрешностям в результате расчетов.)
Отсутствие устойчивости означает, что даже незначительные погрешности в исходных данных приводят к большим погрешностям в решении или к неверному результату.

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

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

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

Сходимость итерационного процесса- этот процесс состоит в том, что для решения некоторой задачи и нахождения искомого значения определяемого параметра (например, корня нелинейного уравнения) строится метод последовательных приближений. В результате многократного повторения этого процесса (или итераций) получаем последовательность значений x1, x2,…, xn,… Говорят, что эта последовательность сходитсяк точному решению x = a, если при неограниченном возрастании числа итераций предел этой

последовательности существует и равен a: Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru - сходящийся численный метод.

4.)

Всякое значение Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , удовлетворяющее условию Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , называется корнем уравнения , а способ нахождения этого значения Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru и есть решение уравнения.

Методы решения уравнений:

  • Прямые (формула Виета для квадратного уравнения и Кардано для кубического и другие)
  • Итерационные – для решения любого уравнения

Общая постановка задачи: Найти действительные корни уравнения Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , где Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru - алгебраическая или трансцендентная функция.

Численное решение уравнения проводится в два этапа:

1 этап. Отделение корней уравнения.

2 этап. Уточнение интересующих корней с заданной точностью ε.

Отделение корней – это определение их наличия, количества и нахождение для каждого из них достаточно малого отрезка [a,b], которому он принадлежит.

На первом этапе определяется число корней, их тип. Определяется интервал, в котором находятся эти корни, или определяются приближенные значения корней.

Задача отделения вещественных корней решается аналитическими и графическими методами.

Аналитические методы основаны на функциональном анализе.

Для алгебраического многочлена n-ой степени (полинома) с действительными коэффициентами вида

Pn(x) = an x n + an-1xn-1 +...+a1x+ a0 = 0, (an >0)

верхняя граница положительных действительных корней Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru определяется по формуле Лагранжа (Маклорена):

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ,

где: k ³ 1 – номер первого из отрицательных коэффициентов полинома;

B – максимальный по модулю отрицательный коэффициент.

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

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Если для этого уравнения по формуле Лагранжа верхняя граница равна R1, то

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru = Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Тогда все положительные корни многочлена лежат в интервале

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ≤x+Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

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

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru и Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ≤xУчесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru = Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru = Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

Постановка задачи:

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

Методом Лагранжа определим границы положительных и отрицательных корней многочлена.

3x8 – 5x7 – 6x3 – x – 9 = 0

k = 1 B = |– 9| an = 3

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru = 4

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru 9x8 + x7 + 6x5 + 5x – 3 = 0

 
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

k = 8 B = 3 an = 9

Отсюда границы положительных корней 0,5 ≤ x+ ≤ 4

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru 3x8 + 5x7 + 6x3 + x – 9 = 0

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru = Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru 9x8 – x7 – 6x5 – 5x – 3 = 0

k = 1 B = 6 an = 9

 
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Следовательно, границы отрицательных корней –2 ≤ x≤ –0,6

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

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

Графически корни можно отделить 2-мя способами:

  1. Построить график функции y = f(x) и определить координаты пересечений с осью абсцисс− это приближенные значения корней уравнения.

  На графике 3 корня. Первый корень x* Î [a,b]
b x2* x3*
x
Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru
x1*
Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru
a
y=f(x)
y
Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Отделение корней на графике f(x).

y=f(x)


  1. Преобразовать f(x)=0 к виду j(x) = y(x), где j(x) и y(x) – элементарные функции, и определить абсциссу пересечений графиков этих функций.

       
   
  На графике 2 корня. Первый корень x1* Î [a,b]
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru
 

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Отделение корней по графикам функций j(x) и y(x).

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Схема алгоритма отделения корней.

5.)

Уточнение корня – это вычисление интересующего корня с заданной точностью e.

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

Метод дихотомии (половинного деления, бисекций)- (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень.

Алгоритм метода.

  1. Вычислить координату середины отрезка [a,b] x = (a+b)/2 и значение ¦(x) в этой точке.
  2. Уменьшить отрезок, отбросив ту его половину, на которой корня нет.

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

если ¦(a) ·¦(x)>0 => x*Î [x,b] => a=x, иначе x*Î [a, x] => b=x

  1. Проверить условие завершения вычислений : длина отрезка не превышает заданную точность и значение функции близко к 0 с заданной точностью:

b-a ≤ ε ∩ |¦(x)| ≤ ε.

Если условие достигнуто, расчет завершен, иначе повторить алгоритм сначала.

 
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Геометрическая интерпретация.

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

b=x

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Схема алгоритма метода бисекций (дихотомии)

6.)Метод Ньютона (касательных)- основан на стратегии постепенного уточнения корня.

 
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Геометрическая интерпретация метода Ньютона.

Уточнение корня – это вычисление интересующего корня с заданной точностью e.

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

На отрезке существования корня выбирается начальное приближение x0. К кривой f(x) в точке А с координатами (x0, f(x0)) проводится касательная. Абсцисса x1 точки пересечения этой касательной с осью ОХ является новым приближением корня.

Из рисунка следует, что x1 = x0 − CB

Из ∆ABC: CD= Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru . Но Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

Следовательно, Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Аналогично, для i-го приближения можно записать формулу итерационного процесса метода Ньютона:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , где x0 Î [a;b]. (3.13)

Условие окончания расчета: Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , (3.14)

где Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru −корректирующее приращение или поправка.

Условие сходимости итерационного процесса:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru (3.15)

Если на отрезке существования корня знаки Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru и Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru не изменяются, то начальное приближение, обеспечивающее сходимость, нужно выбрать из условия

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , x0Î[a;b]. (3.16)

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

Геометрическая иллюстрация выбора начального приближения: график f(x) вогнутый, Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , тогда x0=b, т.к. f(b)>0.

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru Если же выбрать x0=a, то итерационный процесс будет сходиться медленнее или даже расходиться (см. касательную для x0=a).

Геометрическая иллюстрация выбора начального приближения: график

f(x) выпуклый, f ’’(x)<0 , тогда x0 =a, т.к. f(a)<0.

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Схема алгоритма метода Ньютона:

7.)

Метод хорд (секущих).

Этот метод применяется при решении уравнений вида Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , если корень уравнения отделён, т.е. Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru и выполняются условия:

1) Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru (функция Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru принимает значения разных знаков на концах отрезка Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru );

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

Первое приближение корня находится по формуле: Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

Для следующего приближения из отрезков Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru и Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru выбирается тот, на концах которого функция Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru имеет значения разных знаков.

Тогда второе приближение вычисляется по формуле:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , если Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru или Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , если Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

Вычисления продолжаются до тех пор, пока не перестанут изменяться те десятичные знаки, которые нужно оставить в ответе.

Геометрическая интерпретация нахождение решения методом хорд:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

При решении уравнения методом хорд поводится прямая соединяющая концы отрезка [a,b]. Из двух точек А и В выбирается х0. Находится точка пересечения хорды с осью OX. Определяется значение функции в точке пересечения и из найденной точки проводится новая хорда. Этот процесс повторяется до получения необходимой точности.

Формула для n-го приближения имеет вид(х0=а , xn-1=b,xn=x):

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

В методе хорд условием окончания итераций является:

- условие близости двух последовательных приближений : Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ;

- условие малости невязки Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru (величина F(xn) есть невязка, полученная на n-й итерации, а Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru -число , с заданной точностью которого необходимо найти решение).

Описание алгоритма метода хорд
Шаг 1. Ввод a,b,ε.
Шаг 2. X:=a-f(a)×(b-a)/(f(b)-f(a)).
Шаг 3. Если dF2(b)×F(b)<0, то a:=x;
Если dF2(a)×F(a)<0, то b:=x;
Шаг 4. Пересчитать X по формуле шага 2.
Шаг 5. Выполнять шаг 3, пока abs(b-a)<=eps.
Шаг 4.Вывод результата – x.
Опишем назначение переменных и функций, используемых в процедуре Hord
dF2 – значение второй производной в точке Х
F – значение функции в точке Х
Х0 – начальное значение Х
А – левая граница
В – правая граница
Е – точность вычислений
Fa – значение функции в точке А
Fb - значение функции в точке В
Представим в виде структурной схемы.

Блок схема алгоритма метода хорд:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

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

xi=φ(xi-1) , i=1,2,… где i − номер итерации.- последовательное вычисление значений xi по формуле называется итерационным процессом метода простых итераций, а сама формула - формулой итерационного процесса метода.

Алгоритм решения нелинейного уравнения методом
простых итераций:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Если Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , то итерационный процесс сходящийся .

Условие сходимости Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Точное решение x* получить невозможно, так как требуется бесконечный итерационный процесс.

Можно получить приближенное решение, прервав итерационный xi=φ(xi-1) при достижении условия

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ,

где ε - заданная точность; i - номер последней итерации.

В большинстве случаев условие завершения итерационного процесса обеспечивает близость значения xi к точному решению:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Геометрическая иллюстрация метода простых итераций:

1) Итерационный процесс для случая 0< Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru <1 Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru xÎ[a,b].:

 
  Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru 2) Итерационный процесс для случая -1< Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru <1 Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru xÎ[a,b].:

3)Итерационный процесс для случая Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru >1 Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru xÎ[a,b].

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

4)Итерационный процесс для случая Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru £ - 1 Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru xÎ[a,b].

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru

9.) Методы решения систем линейных алгебраических уравнений:

Прямые(конечные) методы решения СЛАУ: (позволяют найти решение за определенное число операций.)
Метод Крамера
Метод обратной матрицы
Метод Гаусса
Итерационные методы решения линейных алгебраических систем: (основанны на использовании повторяющегося (циклического) процесса и позволяющие получить решение в результате последовательных приближений.)
Метод простой итерации или метод Якоби
Метод Гаусса – Зейделя

Постановка задачи

Требуется найти решение системы m линейных уравнений, которая записывается в общем виде как

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ,

Эту систему уравнений можно записать также в матричном виде:

Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru ,

где Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru .

A – матрица системы, Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru – вектор правых частей, Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru – вектор неизвестных.

При известных A и Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru требуется найти такие Учесть погрешность округления при большом количестве арифметических действий практически невозможно. - student2.ru , при подстановке которых в систему уравнений она превращается в тождество.

Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество.

Система называется обусловленной (не вырожденной, не особенной), если определитель системы DA ¹ 0, и тогда система имеет единственное решение.

Система называется не обусловленной (вырожденной, особенной), если DA = 0, и тогда система не имеет решений или имеет бесконечное множество решений.

Система называется плохо обусловленной, если неустранимая погрешность оказывает сильное влияние на решение; у таких систем определитель близок, но не равен 0.

Наши рекомендации