WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СКАЛЯРНЫХ УРАВНЕНИЙ Учебно-методическое пособие по специальности «математика» (010100) ВОРОНЕЖ 2003 2 Утверждено научно-методическим советом математического факультета протокол №7 от 12 мая 2003 года.

Составитель: Трофимов В.П.

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

Рекомендуется для студентов 4 и 5 курсов дневного и вечернего отделений математического факультета, обучающихся по специальности «математика» (010100).

3 Настоящее учебно-методическое пособие предназначено для выполнения лабораторной работы «Численные методы решения скалярных уравнений» по курсу «Методы вычислений» студентами IV-V курсов дневного и вечернего отделений математического факультета. Разработкаможет быть использована для самостоятельной работы студентов и подготовке к экзамену.

Пособие представляет собой существенно переработанный и дополненный вариант методических указаний [5].

Литература 1. Бахвалов Н.С. Численные методы в задачах и упражнениях: Учеб.

пособие / Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков; Под ред. В.А.Садовничего. – М.: Высшая школа, 2000. – 190 с.

2. Плис А.И. Лабораторный практикум по высшей математике: Учеб.

пособие для втузов / А.И.Плис, Н.А.Сливина. – 2-е изд., перераб. и доп. – М.:

Высшая школа, 1994. – 416 с.

3. Загускин В.Л. Справочник по численным методам решения уравнений/ В.Л.Загускин. – М.: Физматгиз, 1960. – 216 с.

4. Люстерник Л.А. Краткий курс функционального анализа / Л.А.Люстерник, В.И.Соболев. – М.: Высшая школа, 1982. – 328 с.

5. Методические указания по методам вычислений и вычислительной практике. Часть I / Сост. Г.С.Аброськина, В.П.Трофимов. - Воронеж.: Воронеж.

гос. ун-т, 1987. – 20 с.

Обозначения R - множество вещественных чисел;

N – множество натуральных чисел;

[ ba; ] C - банахово пространство функций непрерывных на R.

;( ba ) k )( C [ ba; ] - пространство функций, имеющих на непрерывные ;( ba ) k производные до порядка включительно.

1. Постановка задачи Рассмотрим уравнение xf )( = 0, (1) : Xf X где R определена и непрерывна на некотором промежутке * Xx вещественной прямой R. Число называется решением (корнем) * f xf )( = уравнения (1) или нулем функции если. Если в окрестности корня k x* f xf )( (x -= x*) g(x) k xg )( 0, то функция представима в виде, где N и k k = 1 x* число называется кратностью корня. Если, то корень называется простым.

x* k f Замечание 1. Корень гладкой функции имеет кратность, если j)( * k )( * xf )( 0, j == 0,1,,k -1 xf )( и.

-xf )( a x += a10 xnn + + a + ax, xf )( Если является многочленом:

-1 nn ai =,0,ni, R, то уравнение (1) называется алгебраическим. Уравнения, не являющиеся алгебраическими, принято называть трансцендентными.

Специальные свойства многочленов позволяют построить большое число методов решения алгебраических уравнений. Наиболее часто используют метод выделения действительных множителей (методы Лина, Фридмана), метод Лобачевского (см. [3]).

Численное решение уравнения (1) обычно состоит из двух этапов.

На первом этапе осуществляют отделение (локализацию) корней - находят [ ba; ] f отрезок R (возможно меньшей длины), на концах которого функция af )( f (b) < принимает значения разных знаков:. На втором этапе отыскивают ~ [ax ;b] приближенное значение корня с заданной абсолютной точностью :

* ~ xx <-.

f [ ba; ] af )( f (b) < Если непрерывна на и, то по теореме Больцано[ ba; ] Коши на отрезке существует, по крайней мере, один корень уравнения (1).

)1( Cf xf )( ;( ba ) Если и производная сохраняет знак внутри интервала, то ;( ba ) * [ax ;b] уравнение (1) имеет единственный простой корень.

f [ ba; ] Внимание! Непрерывная функция может иметь на отрезке корни и af )( f (b) < не удовлетворять условию (см. рис.1).

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

xf )( Табличный способ состоит в определении знаков функции в узлах { h > 0,, j = 0,,1 N} += jh некоторой сетки, выбор параметров которой j Nh,, xf )( зависит от особенностей функции. Если в построенной таблице xf )( )( ff ( ) < 0 [ ; ] значений функции имеем, то на отрезке kk +1 kk +, kk +находится хотя бы один корень уравнения (1). Если узлы близки, то можно надеяться, что корень между ними один. Однако в этом нужно убедиться с помощью дополнительного исследования. Выявить по таблице корни четной кратности крайне сложно.

Замечание 2. При наличии дополнительной информации о свойствах : Xf функции R на первом этапе находят грубые границы корней – отрезок [ ;Mm ] X, содержащий все корни уравнения (1) (см. рис. 2). Затем находят отрезки, каждый из которых содержит только один корень.

y * * x1 x0 m M = fy x)( Рис. [ ba; ] x* Пусть уравнение (1) имеет на отрезке единственный корень и k [ ba; ] xf )( (x -= x*) g(x) xg )(, где функция сохраняет знак на. В этом случае xf )( существует качественное различие в поведении функции в окрестности k xf )( [ ba; ] k корня: при нечетном функция меняет знак на, а при четном - нет.

Таким образом, только после того как известны ответы на вопросы о [ ba; ] существовании, единственности и кратности корня на отрезке, можно переходить к выбору численного методарешения уравнения (1).



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

Известные прямые методы применимы только для узкого класса специальных xf )( функций. Основными способами решения уравнения (1) являются итерационные методы. Итерационный метод позволяет найти такую n)( {x } x* последовательность приближений, которая сходится к корню уравнения n)( * n)( lim = xx x (1): (в этом случае называется n -ым приближением к корню n n)( n+1( ) x* n x x ). Если для любого два последовательных приближения и x* располагаются по разные стороны от корня, то метод называется двусторонним, а если по одну сторону – односторонним.

Важнейшей характеристикой итерационных методов является скорость p сходимости. Итерационный метод имеет скорость сходимости (порядок), p если есть наибольшее положительное число, для которого существует такое n C > 0, что для любого N:

p +1( ) * ) xx - C x(nn - x*.

n)( * Величину - xx C называют погрешностью n -ого шагаитераций. Число C называют константой асимптотической ошибки метода (обычно можно f p = 1 < C < оценить с помощью производных функции ). Если и, то говорят, что метод сходится со скоростью геометрической прогрессии со C p = 2 C > 0 - знаменателем (имеет линейную скорость сходимости). Если ( любое), то скорость сходимости называется квадратичной.

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

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

(~) xf Однако это не всегдатак. Даже если велико, это не обязательно означает, ~ x что является грубым приближением к корню. Действительно, если умножить r уравнение (1) на произвольное число, то получается эквивалентное rf (~) x rf x)( = уравнение, причем число можно сделать сколь угодно большим r или сколь угодно малым за счет выбора множителя. Кроме того, имеет место еще одно заблуждение: если при реализации итерационного метода выполнено +1( ) (nn ) n)( * xx <- xx <- условие, то также справедливо и неравенство.

Однако в общем случае это утверждение является ошибочным.

> Пусть абсолютная точность, с которой требуется найти n)( * xx <- x* корень уравнения (1):. Тогда условием останова для +1( ) (nn ) xx <- двустороннего метода является выполнение условия (при реализации алгоритма двустороннего метода строится последовательность вложенных отрезков, содержащих искомый корень уравнения (1)).

Для односторонних методов мы не можем использовать такой контроль вычислений. В этом случае необходимо ввести некоторую относительную характеристику точности вычислений. Будем говорить, что корень уравнения (1) n)( > 0 x найден с относительной точностью, если вычислено приближение n)( * xx <- x(0) - x*. Это означает, что вычисления продолжаются такое, что до тех пор, покарасстояние от нулевого приближения до искомого корня не будет уменьшено в раз. Для одностороннего метода часто в качестве условия n+1( ) (xf ) < останова принимают одновременное выполнение двух неравенств и +1( ) (nn ) xx <-.

К критериям окончания счета можно добавить условие (например, 1( ) (nn ) 1) xx x(n) -- x(n-+ > ), позволяющее выявлять расходимость метода на ранних этапах итерационного процесса. Однако применение такого рода критериев может привести к преждевременному окончанию вычислений, поскольку приближения, прежде чем начать сходиться к корню уравнения (1), могут вначале процесса расходиться.

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

отн +1( ) (nn ) xx - + x(n) (. 2) абс отн Использование критерия (2) основано на следующих соображениях.

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

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

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

отн Замечание 3. Для систем представления чисел с плавающей запятой в ЭВМ имеет место следующее фундаментальное свойство: расстояние между числом r и masheps r p macheps r ближайшим к нему числом не меньше и не больше, p если только само число или соседнее число не равно нулю. Здесь - основание macheps - машинно-зависимый параметр, системы счисления ЭВМ, характеризующий относительную точность машинной арифметики с плавающей macheps запятой, является наименьшим числом с плавающей запятой, для.1 0 + macheps > 1.0 macheps p которого выполнено неравенство:. Значение равно macheps = p1-t t - расстоянию от 1.0 до левого соседнего числа и само значение ( количество разрядов мантиссы) представляет собой расстояние от 1.0 до правого соседнего числа.





n)( n)( x = macheps x p Поэтому если окажется меньше, то при отн абс неравенство (2) никогда не будет выполняться и, следовательно, итерационный процесс может не завершиться. Отсюда получаем критерий точности, обеспечивающий максимальную близость двух соседних итераций (соседних чисел):

1( ) (nn ) 1) xx <- macheps max(x(n++, x(n) ).

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

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

Как уже отмечалось выше, применение критерия n)( (xf ) зн 3( ) n)( x не может гарантировать вычисления приближенного значения корня с заданной точностью; то же самое можно сказать и о критерии (2) для односторонних методов. Однако на практике для односторонних методов одновременное применение критериев (2) и (3) (если,, достаточно абс отн зн малы) дает вполне удовлетворительные результаты.

xf )( Внимание! В случае, когда производная функции вблизи x* корня мала по абсолютной величине, то есть график функции почти xf )( горизонтален в окрестности корня, любое небольшое возмущение xf )( + > 0 x* (например,, ) приводит к заметному изменению корня.

Подобная неустойчивоcть характерна для многочленов высоких степеней.

3. Метод деления пополам Этот метод называют еще методом половинного деления, дихотомией, методом бисекций или методом вилки. Метод деления пополам - итерационный метод, алгоритм которого имеет вид:

+1( ) (nn ) ax += b(n) - a(n)),( )( (nn 1) (n) 1) [ xa ],; если (af ) f (x(n++ )< 0, 1( ) (nn ++ 1) [ ;ba ]= 4( ) 1( ) (nn ) (n++ 1) [ bx ],; если (xf ) f (b(n))< 0, 0( ),01,2,, an == a, b(0) = b.

n)( (xf )= 0 n Если для некоторого, то процесс вычислений прекращают и (* n) xx полагают.

Метод деления пополам является двусторонним. Условием останова +1( ) (nn ) xx <- алгоритма (4) является выполнение неравенства, где > 0 заданная точность вычислений (см. рис. 3).

y = fy x)( 2( ) x* x 0( ) )0( a b x )1( (0) ax += b(0) )( / Рис. Cf Теорема 1. Пусть функция и на концах отрезка ;( ba ) [ ba; ] af )( f (b) < принимает значения разных знаков:. Тогда x* [ ba; ] последовательность (4) сходится при n к решению уравнения (1) и справедлива оценка погрешности - ab n)( * xx - (. 5) 2n [ ba; ] Замечание 4. Если на отрезке имеется несколько корней уравнения (1), то метод деления пополам сходится к одному из них.

Теоретически алгоритм (4) позволяет найти корень уравнения (1) с любой n )( абсолютной точностью. Оценим число итераций, необходимое для вычисления корня уравнения (1) с заданной абсолютной точностью. Из (3) - ab - ab n)( * xx - < n > log2 и, следовательно, имеем. Отсюда 2n - ab n )( log2.

Это означает, что для получения каждых трех верных знаков необходимо около 10 итераций.

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

Рассмотрим, как это можно сделать при вычислении среднего + ba a b арифметического двух чисел и (очередного приближения метода + ba c = деления пополам). Возможны два способавыполнения этой операции: и - ab ac +=. Первая формула требует на одну операции сложения меньше, чем вторая, но с точки зрения точности не всегдадает лучший результат. Нетрудно установить наилучшую формулу для вычисления среднего арифметического двух a b чисел и :

+ ba - ab c = ac += sign a)( sign(b) если ( ), то.

иначе 2 Для метода деления пополам применение второй формулы n)( n)( a b предпочтительнее, поскольку при увеличении числа итераций знаки и становятся одинаковыми до окончания итерационного процесса (исключением является случай, когдаискомый корень равен нулю).

xf )( Замечание 6. Обычный способ проверки изменения знакафункции на [ ba; ] af )( (bf ) < отрезке состоит в проверке условия. Однако если значения )(af )(bf af )( (bf ) может стать машинным и близки к нулю, то произведение нулем, и этот способ окажется неприемлемым. Поэтому проверку изменения знака функции лучше выполнять следующим образом:

bf )( af )( < abs( f b)( ).

4. Метод простых итераций (последовательных приближений) Заменим уравнение ему (1) эквивалентным уравнением = xx ).( (6) Замечание 7. Уравнения (1) и (6) называются эквивалентными, если корни уравнения (1) являются корнями уравнения (6) и наоборот. Переход от уравнения (1) к (6) можно осуществить положив, например, )( xx += (x) f (x), x)( где - некоторая знакопостоянная функция.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.