Численные методы решения инженерных задач

Тема 1

Численные методы решения инженерных задач

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

Численные методы – это методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, выполняемыми на ЭВМ.

При применении численных методов решение задачи оказывается, как правило, приближенным. Это объясняется тем, что точное решение многих задач неизвестно.

Кроме того, даже при наличии точного метода часто используются приближенные методы, в частности, по следующим причинам:

- точное решение очень трудоемко, а приближенное решение при существенно меньшем объеме вычислений оказывается вполне приемлемым;

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

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

Основные источники и типы погрешностей

Элементы теории погрешностей

Неустранимые погрешности:

1. Несоответствие математической модели (задачи) изучаемому реальному явлению.

2. Погрешность исходных данных (входных параметров).

Устранимые погрешности:

3. Погрешность метода.

4. Ошибки округления в действиях над числами

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

Приближенные числа и действия над ними

Пусть А – точное значение некоторой величины, a – приближенное значение (число), заменяющее А в вычислениях.

Абсолютная погрешность (ошибка) числа

(1.1)

- предельная абсолютная погрешность - всякое число, не меньшее абсолютной погрешности числа.

Следовательно, точное число А заключено в границах

, (1.2)

Абсолютная погрешность недостаточна для характеристики точности вычислений, например м и м

Относительная погрешность числа

(1.3)

- предельная относительная погрешность, не меньшая относительной погрешности числа.

Обычно относительная погрешность определяется в процентах

(1.4)

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

Теорема 1. Абсолютная погрешность суммы или разности приближенных чисел равна сумме абсолютных погрешностей чисел.

(1.5)

Теорема 2. Относительная погрешность произведения или частного двух приближенных чисел, отличных от 0, не превышает суммы относительных погрешностей этих чисел.

; (1.6)

Некоторые следствия из теорем

;

(1.7)

; .

Системы счисления – это совокупность приемов и правил для обозначения и наименования чисел.

Различают позиционные и непозиционные системы счисления.

Примером непозиционной системы счисления является римская система (I – 1, V – 5, т.е. цифры сохраняют значение числа вне зависимости от положения цифры).

Арабская система записи чисел – позиционная.

В позиционной системе с основанием β запись

(1.8)

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

Представление числа с плавающей запятой

, (1.9)

где М – мантисса числа х,

β – основание системы счисления,

b – целое число.

Значащие и верные цифры

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

Пример: 127, 56 – 5 значащих цифр

0, 028 – 2 значащих цифры

0, 3050 – 4 значащих цифры

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

Пример: у числа0, 230245 значащих цифр

0, 23024 0, 0001 (0, 00005 < Δ = 0, 0001 < 0, 0005) - 3 верных цифры

0, 23024 0, 0006 (0, 0005 < Δ = 0, 0006 < 0, 005) - 2 верные цифры

Округление чисел

Округление числа a – это замена его числом a₁ с меньшим количеством значащих цифр.

Число a₁выбирают так, чтобы ошибка округления была минимальной

│ a₁ - a│ = min.

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

Тема 2

Абсолютное отклонение

(2.1)

Среднеквадратичное отклонение

(2.2)

Интерполяция

Пусть на отрезке задана сетка с узлами интерполяции x₀, x₁,..., x_n.

В узлах сетки заданы значения функции y₀=f(x₀), y₁=f(x₁),..., y_n=f(x_n) т.е. заданы точки с координатами (x_i, y_i), i=0, 1,..., n.

Задача интерполирования заключается в построении многочлена (полинома) F_m(x) степени m, который в узлах интерполяции принимает те же значения, что и заданная функция f(x).

Если многочлен строится на части узлов, то такая интерполяция называется локальной, если на всех узлах – то это глобальная интерполяция.

Если значение х выходит за пределы отрезка интерполирования, то задача отыскания значения функции в этой точке называется задачей экстраполирования.

...

Разности высших порядков

...

(2.6)

...

где i = 0, 1,..., n-k

Многочлен Ньютона будем искать в следующем виде

N(x)=a₀+ a₁(x-x₀)+ a₂(x-x₀)(x-x₁)+...+ a_n(x-x₀)(x-x₁)∙...∙ (x-x_n-1)=

= (2.7)

Из условия N(x_i) = y_i = f(x_i) определяем

N(x₀) = a₀ = y₀

N(x₁) = a₀ + a₁(x₁-x₀) = a₀+ a₁h = y₁

N(x₂) = a₀ + a₁(x₂-x₀) + a₂(x₂-x₀)(x₂-x₁)= a₀ +2a₁h+2a₂h ²= y₂

...

Отсюда

a₀ = y₀,

(2.8)

...

Введем обозначение и подставим его и (2.8) в формулу (2.7).

Выполняя преобразования, получим

(2.9)

Для повышения точности целесообразно применять полученную формулу Ньютона не для всего интервала [x₀, x_n], а для x₀ ≤ x ≤ x₁. Для других значений аргумента x_i ≤ x ≤ x_i+1 вместо x₀ взять x_i.

Тогда, в общем виде получим 1–й интерполяционный многочлен Ньютона для интерполирования вперед, т.е. x₀, x₀ + h,..., x₀ + nh.

(2.10)

Эта формула используется для вычисления значений функции в точках левой половины отрезка [x₀, x_n], т.к. разности вычисляются через значения функции y_i, y_i+1, ..., y_i+k при i+k < n и при больших i нельзя вычислить разности высших порядков, входящих в (2.10).

Для правой половины отрезка лучше вычислять справа налево и принимать обозначение .

Получаем 2–й интерполяционный многочлен Ньютона для интерполирования назад, т.е. x_n, x_n - h,..., x_n - nh.

(2.11).

При точном вычислении формулы Лагранжа и Ньютона порождают один и тот же многочлен.

Тема 3

Численное интегрирование

Геометрическое истолкование определенного интеграла: интеграл численно равен площади, покрываемой ординатами графика f(x), т.е. площади криволинейной трапеции, ограниченной осью абсцисс, отрезками прямой x = a, x = b и графиком подынтегральной функции.

где F – первообразная.

Если первообразную найти сложно или невозможно, а также, если f(x) задана таблично или графиком, применяется численное интегрирование.

Формула прямоугольников

Промежуток интегрирования [a, b] делим точками x_1,x_2,..., x_n-1 на n равных частей; длина каждой

h=(b-a)/n.

Т.е. x₀= a, x_n= b, x_i = a + i h, i = 0, 1, ..., n..

Пусть y ₀ = f(x₀), y _i = f(x_i), ..., y _n = f(x_n).

I ≈ (b - a) f(a) – формула левых прямоугольников

I ≈ (b - a) f(b) - формула правых прямоугольников.

(3.1)

(3.2)

Выражения (3.1), (3.2) дают площади ступенчатых фигур.

Точность формул увеличивается с увеличением n.

Формула трапеций

Промежуток интегрирования [a, b] делим точками x_1,x_2,..., x_n-1 на n равных частей; длина каждой h=(b-a) / n,

Т.е. x₀ =a, x_n b, x_i = a + i h, i = 0, 1, ..., n..

Пусть y ₀ = f(x₀), y _i = f(x_i), ..., y _n = f(x_n).

– формула трапеций

(3.4)

Выражение (3.4) дает общую площадь трапеций.

Оценка погрешности

Формулы (3.3), (3.5), (3.7) – 2-го и 4-го порядка точности можно применять, если существует и достаточно легко вычисляются (оцениваются) производные.

На практике, т.к. это бывает редко, применяется ''двойной просчет''.

Допустим, интеграл вычислен дважды при различных значениях шага (h и h / 2).

Пусть интеграл I_n вычислен при h, I_2n – при h / 2.

;

Остаточные члены ; ,

где - среднее арифметическое разностей соответствующего порядка.

Шаг интегрирования выбирается так, чтобы выполнялось неравенство

, (ε задано).

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

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

Вместо подынтегральной функции f(x) интегрируем интерполя-ционный многочлен Лагранжа для равноотстоящих узлов.

h =(b-a) / n.

x_i = a + i h, i = 0, 1, ..., n.

y ₀ = f(x₀), y _i = f(x_i), ..., y _n = f(x_n).

, (3.8)

где H_i – весовые коэффициенты (Котеса)

(3.9)

При n = 1 получим формулу метода трапеций, при n = 2 – метода Симпсона.

Для метода трапеций: n = 1, i = 0, 1.

i = 0

i = 1 .

Полученные формулы подставим в (3.8)

Для метода Симпсона: n = 2, i = 0, 1, 2.

i = 0

i = 1

i = 2

После подстановки в (3.8) получим

Тема 4

Методы решения СЛАУ

Методы решения СЛАУ подразделяются на точные и итерационные.

Точные – это методы, которые определяют решение при помощи конечного числа арифметических операций.

При этом, если исходные данные и вычисления точны, то получается точное решение (методы Крамера, Гаусса).

Точные методы выполняются в два этапа:

- преобразование исходной СЛАУ к более простому виду;

- решение упрощенной системы и получение неизвестных.

Метод Гаусса

(последовательного приближения неизвестных)

где А = ; x = ; b = ;

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

2. Находим неизвестные, начиная с x_n, x_n-1, x_n-2,..., x₂, x₁.

Метод прогонки

(модификация метода Гаусса для систем

с 3-х диагональной матрицей коэффициентов)

, i= 1, 2, ..., n, (4.3)

Каждое i – уравнение содержит не более 3 неизвестных x_i-1, x_i, x_i+1.

; (4.4)

Последовательные исключения выполняются так:

Из ''0'' уравнения выражаем и подставляем в 1-е уравнение .

Затем выразим x₁ через x₂ и подставим во 2-е уравнение и т.д.

Будем считать, что соотношение между x_i и x_i+1 известно

, (4.5)

тогда

(4.6)

Подставим (4.6) в i – уравнение и решим относительно x_i.

Выразим (4.7)

Сравнив (4.7) и (4.5), получим прогоночные коэффициенты

, (4.8)

При i = 0 из (4.5) получим .

сравнив с (4.4) получим

, (4.9)

Этапы метода прогонки

1) Прямой ход: каждое i – неизвестное выражается через i+1– е с помощью прогоночных коэффициентов (4.8) и (4.9) (i =0, 1, ..., n-1)

2) Обратный ход: с помощью (4.5) определим x_n, затем

и сравним с последним уравнением (4.3).

Выразив x_n, получим

(4.10)

Далее, используя (4.5) и формулы прогоночных коэффициентов (4.8) и (4.9), находят x_n-1, x_n-2,..., x₁, x₀.

Тема 5

Метод Гаусса - Зейделя

В этом методе уточненное значение x₁ сразу же используется для вычисления x₂, а x₁ и x₂ для вычисления x₃ и т.д.

Зададимся начальным приближением неизвестных.

Обычно принимают , , ..., .

Начальные приближения подставляют в 1-е уравнение системы (5.1).

затем подставляем , , ..., во 2-е уравнение

Подставляем , , , ...,

Подставляем , , ..., , выполним 2-ю итерацию.

Приближения с номером k определим по формуле

(5.6)

...................

Т.е. координаты вектора определяют по формуле

, i = 1, 2, ..., n (5.7)

Для сходимости метода необходимо, чтобы

1) все диагональные элементы были отличны от 0 (a_ii ≠ 0);

2) диагональные элементы значительно преобладали над остальными коэффициентами матрицы А.

В общем случае критерий окончания итерационного процесса при заданной допустимой погрешности ε > 0 определяется:

- по абсолютным отклонениям в виде

, i = 1, 2, ..., n

- по относительным разностям в виде

(5.8)

Тема 6

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

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий только один корень, т.е. f(а)∙ f(b) < 0.

Для определенности будем считать f(а) < 0, f(b) > 0.

Найдем значение f(c₀), где - начальное приближение. Последующие приближения будем определять по формуле , а = с₀, если f(c₀)∙ f(b) < 0,

или по формуле , b= с₀, если f(a)∙ f(c₀) < 0 и т.д.

Условие прекращения итерационного процесса .

Метод имеет малую скорость сходимости.

Погрешность оценивается выражением

(6.4)

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

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий только один корень, с₀ – начальное приближение.

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

Вместо интерполяции осуществляется экстраполяция с помощью касательной к кривой в данной точке (ее пересечение с осью абсцисс).

В основе лежит разложение в ряд Тейлора

или

Дано f(x) = 0, x Î [a, b],

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

Уравнение касательной в т. М₀(c₀, f(c₀))

Первое приближение c₁– абсцисса точка пересечения касательной к точке М₀ с осью х (c₁, 0).

Из выражения

получим и т.д.

, n = 0, 1, 2, … (6.9)

Замечание: начальное приближение c₀ целесообразно выбирать так, чтобы

(6.10)

Теорема (достаточное условие сходимости):

Пусть f(x) определена и дважды дифференцируема на [a, b], причем f(a) f(b)< 0, а и сохраняют знак на [a, b]. Тогда, исходя из начального приближения , удовлетворяющего (6.10), последовательность (6.9) сходится к единственному на [a, b] решению x = c уравнения (6.1).

Трудности метода Ньютона состоят в определении:

1) начального приближения x = c₀, которое должно находиться вблизи корня уравнения;

2) первой производной , отличной от 0, что не требуется в первых двух методах.

Объем вычислений метода Ньютона больше, но скорость сходимости выше.

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

Оценка погрешности n – го приближения

(6.11)

где .

При этом быстрая сходимость обеспечена, если начальное приближение c₀ удовлетворяет неравенству

(6.12)

Метод простой итерации

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий только один корень.

Уравнение (6.1) представим в виде

x = j (x) (6.13)

Выбираем начальное приближение x = c₀ и, подставив в (6.13), находим следующее приближение c₁ = j (c₀) и т.д.

По аналогии

с_n₊₁ = j (c_n), n = 0, 1, 2, … (6.14)

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

Строим графики функций y = x и y = j (x) (левая и правая части уравнения (6.13)).

Каждый действительный корень с является абсциссой точки пересечения кривой y = j (x) и прямой y = x.

Оценка погрешности n – го приближения

, (6.15)

где .

Тема 7

Метод простой итерации

Метод простой итерации для СНУ является развитием аналогичного метода для решения одного уравнения. Он основан на допущении, что систему (7.1) можно привести к виду

(7.2)

………

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

(7.3)

………

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

, i = 1, 2, …, n (7.4)

Недостаток метода:

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

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

Метод Ньютона

Совокупность аргументов x₁, x₂, …, x_n системы (7.1) можно рассматривать как n - мерный вектор, а совокупность функций f₁, f₂, …, f_n как n - мерный вектор – функцию.

, .

Уравнение (7.1) можно записать в матричном виде

(7.5)

Приближенно заменим систему (7.5) линейной алгебраической системой.

Для этого разложим в ряд Тейлора по степеням , где , и опустим в разложении члены второго и более высоких порядков.

(7.6)

Определителем полученной системы линейных уравнений (7.6) относительно является определитель матрицы Якоби (якобиан), подсчитанный для

(7.7)

Для существования единственного решения системы (7.1) якобиан системы (7.7) должен быть отличен от 0 на каждой итерации.

Если , то (7.6) можно переписать

и т.д. (7.8)

Таким образом,

, k = 0, 1, 2, … (7.9)

, i = 1, 2, …, n ...

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

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

. (7.10)

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

, k = 0, 1, 2, … (7.11)

Литература

1. Березин И.С., Жидков Н.П. Методы вычислений. –М.: Физматгиз, 1962

2. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. -М., 1963

3. Калиткин Н.Н. Численные методы. –М.,: Наука, 1978.

4. Самарский А.А., Гулин А.В. Численные методы. –М.,: Наука, 1989

Тема 1

Численные методы решения инженерных задач

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

Основные источники и типы погрешностей

12 3 4 5 6 Следующая ⇒