Файл: А.В. Матисов Решение нелинейных уравнений.pdf

9

будет расположена недалеко от корня x=с. Для определения этой точки х имеем уравнение f(x0)+f '(x0) (x-x0)=0, откуда

Каждое следующее приближение вычисляется по рекуррентной формуле

где n = 0, 1, 2, ….

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

Рис. 2.5. Графическая иллюстрация метода касательных

Если за начальное приближение принять точку (х'), в которой знаки f(х') и f ''(х') противоположны, то в результате вычислений получим точку (х''), которая не является приближением к корню и даже выходит за интервал изоляции (рис. 2.5).

1.Выберем точность вычислений корня Е.

2.Установим границы интервала изоляции x1 и х2.

3.Возьмем начальное приближение х0, принадлежащее [x1, x2].

4.Вычислим F=f(x0) и F2=f ''(x0).

5.Если F× F2<0, то идти к пункту 3.

6.Присвоим x=x0.

7.Вычислим х=x-f(x)/f '(x).

8.Вычислим y=f(x).

9.Если |у|≥Е, то идти к пункту 7.

10

10.Искомый корень равен х и функция равна у.

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

2.3.4. Метод хорд

Метод хорд по эффективности и идее можно сравнить с предыдущим. Пусть имеется интервал изоляции корня [x1, x2]. Функция f(x) имеет на [x1, x2] непрерывные производные f '(х) и f ''(x). Точки М1(х1, у1) и М2(x2, у2) (рис. 2.6), где y1=f(x1) и y2=f(x2), соединим хордой М1М2, которая пересечет ось абсцисс в точке N(x3, 0). Уравнение этой хорды

( x-х1 ) / ( х2- х1 ) = ( y-y1 ) / ( у2-у1 ). (2.12)

При у=0 получим

Значение х=хЗ является первым приближением к искомому корню. Найдем следующее приближение. Вычислим уЗ=f(хЗ). В зависимости от знака f(x3) новым интервалом изоляции будет либо [x1, x3], либо [x3, x2]. В нашем примере (рис. 2.6) корень находится в интервале [x3, x2]. Как видно из рис. 2.6, второе приближение корня определяется с помощью

хорды М3М2.

Алгоритм метода хорд:

1.Выберем точность вычислений корня Е.

2.Установим границы интервала изоляции х1 и х2.

3.Вычислим y1=f(x1) и y2=f(x2).

4.Вычислим приближение x3=x1-y1 (х2-х1)/(у2-у1).

5.Вычислим |уЗ|=f(х3).

6.Если y3<E, то идти к пункту 9.

7.Если у1 у3<0, то x2=x3 и y1=y3, иначе х1=х3 и y1=y3.

8.Идти к пункту 4.

9.Искомый корень равен х3 и функция равна у3.

11

Рис. 2.6. Графическая иллюстрация метода хорд

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

2.3.5. Метод Монте-Карло (статистических испытаний)

Метод заключается в использовании случайных чисел для уточнения корня нелинейной функции. Равномерно-распределенные случайные числа обычно генерируются ЭВМ в отрезке [0, 1], причем любое значение из этого отрезка равновероятно. Перевод случайных чисел из интервала [0, 1] на интервал [а, b] производится по формуле

где Xi – случайное число в интервале [а, b]; Ui – случайное число в интервале [0, 1].

Рассмотрим алгоритм метода. Предполагаем, что решена задача отделения корней и интервал [а, b] (рис. 2.7) является интервалом изоляции корня, а производная f '(x) в интервале [а, b] знак не меняет.

1.Выберем точность вычислений корня Е.

2.Установим границы изоляции корня a и b.

3.Генерируем x случайным образом на интервале [a, b].

4.Вычисляем значение функции F=f(x) в случайной точке x.

12

5.Если |F|≥Е, то идти к пункту 3.

6.Искомый корень равен х и функция равна F.

Рис. 2.7. Иллюстрация к методу Монте-Карло

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

На практике чаще применяют разновидность метода Монте-Карло, ограничивая выполнение алгоритма числом шагов итераций (например, N = 1 000, 10 000, 1 000 000 и т.д. – в зависимости от конкретных условий), после выполнения которых результатом считают ту точку х, в которой функция F=f(x) имеет меньшее значение по сравнению со всеми другими, полученными в ходе испытаний.

Алгоритм метода Монте-Карло по числу испытаний:

1.Установим число испытаний N.

2.Установим границы интервала изоляции a и b.

3.Генерируем x случайным образом на интервале [a, b].

4.Вычисляем значение функции F=f(x) в случайной точке x.

5.Установим счетчик испытаний I=1.

6.Если I>N, то идти к пункту 10.

7.Генерируем x1 случайным образом на интервале [a, b].

8.Вычисляем значение функции F1=f(x1) в случайной точке x1.

9.Если |F|≥|F1|, то F=F1 и х=х1 (запомним новые значения).

10.I=I+1.

11.Идти к пункту 6.

12.Искомый корень равен х и функция равна F.

13

3. ВАРИАНТЫ ЗАДАНИЙ

Найти с точностью 0,000001 наименьший корень уравнения. Перед применением указанного в варианте метода провести отделение корней. Сделать проверку найденного решения.

Варианты заданий приведены в табл. 3.1.

Таблица 3.1

Варианты заданий

СПИСОК ЛИТЕРАТУРЫ

1.Инженерные расчеты на ЭВМ: Справ. пособие / Под ред. В.А.Троицкого. – Л.: Машиностроение. Ленингр. отд-ние, 1979. – 288 с.

2.Тихонов А.Н. Вводные лекции по прикладной математике / А.Н.Тихонов, Д.П.Костомаров. – М.: Наука. Гл. ред. физико-математ.

лит., 1984. – 192 с.

3.Васильков Ю.В. Компьютерные технологии вычислений в математическом моделировании: Учеб. пособие / Ю.В.Васильков, Н.Н.Василькова. – М.: Финансы и статистика, 1999. – 256 с.

4.Дьяконов В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. – М.: Наука. Гл. ред. физико-

математ. лит., 1987. – 240 с.

5.Мак-Кракен Д. Численные методы и программирование на Фортране / Д.Мак-Кракен, У.Дорн – 2-е изд., стереотипное. – М.: Мир, 1977. – 584 с.

6.Боглаев Ю.П. Вычислительная математика и программирование: Учеб. пособие для студентов втузов. – М.: Высш. шк., 1990. – 544 с.