Численные методы решения нелинейного уравнения

С одним неизвестным

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

Дано уравнение F(x)=0. Это - общий вид нелинейного уравнения с одним неизвестным. Как правило, алгоритм нахождения корня состоит из двух этапов.

Отыскание приближенного значения корня или отрезка на оси абсцисс, его содержащего.

Уточнение приближенного значения корня до некоторой точности.

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

2.2. Шаговый метод

Дано уравнение F(x)=0. Задан интервал поиска [x₀,x₁]. Требуется найти интервал [a,b] длиной h, содержащий первый корень уравнения, начиная с левой границы интервала поиска.

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

Установить интервал [a,b] на начало интервала поиска (a = x₀).

Определить координату точки b (b = a+h), а также значения функции в точках a и b: F(a) и F(b).

Проверить условие F(a)*F(b)<0. Если условие не выполнено - передвинуть интервал [a,b] на один шаг (a = b) и перейти к пункту 2. Если условие выполнено - закончить алгоритм.

Решением являются координаты точек a и b. Отрезок [a,b] содержит корень уравнения, поскольку функция F(x) на его концах имеет разные знаки (рис. 3).

Рис. 3

Найдя первый корень, можно продолжить поиск корней по тому же алгоритму. В этом случае определяются отрезки, содержащие все корни уравнения на интервале поиска [x₀,x₁]. Если на всем интервале поиска ни разу не было выполнено условие F(a)*F(b)<0, то данный интервал вообще не содержит корней.

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

Метод основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до тех пор, пока не будет достигнута заданная точность e. Пусть задан отрезок [a,b], содержащий один корень уравнения. Этот отрезок может быть предварительно найден с помощью шагового метода.

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

Определить новое приближение корня x в середине отрезка [a,b]: x=(a+b)/2.

Найти значения функции в точках a и x: F(a) и F(x).

Проверить условие F(a)*F(x)<0. Если условие выполнено, то корень расположен на отрезке [a,x] (рис. 4). В этом случае необходимо точку b переместить в точку x (b=x). Если условие не выполнено, то корень расположен на отрезке [x,b]. В этом случае необходимо точку a переместить в точку x (a=x).

Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до тех пор, пока не будет выполнено условие ïF(x)ï<e.

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

Задан отрезок [a,b], содержащий корень уравнения F(x)=0. Уточнение значения корня производится путем использования уравнения касательной. В качестве начального приближения задается тот из концов отрезка [a,b], где значение функции и ее второй производной имеют одинаковые знаки (т.е. выполняется условие F(x₀)*F¢¢(x₀)>0). В точке F(x₀) строится касательная к кривой y = F(x) и ищется ее пересечение с осью x. Точка пересечения принимается за новую итерацию. Итерационная формула имеет вид:

Итерационный процесс продолжается до тех пор, пока не будет выполнено условие ïF(x)<eï, где e - заданная точность.

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

Метод основан на замене исходного уравнения F(x)=0 на эквивалентное x=j(x). Функция j(x) выбирается таким образом, чтобы на обоих концах отрезка [a,b] выполнялось условие сходимости êj¢(x) ê< 1. В этом случае в качестве начального приближения можно выбрать любой из концов отрезка. Итерационная формула имеет вид

Итерационный процесс продолжается до тех пор, пока не будет выполнено условие ïF(x)<eï, где e - заданная точность.

Реализация в пакете Excel

В качестве примера рассмотрим уравнение x² - 4x + 3 = 0. Интервал поиска [0;3,3], шаг h = 0,3. Решим его, используя различные численные методы, а также специальные возможности пакета Excel - «Подбор параметра» и «Поиск решения».

Последовательность действий (см. рис. 5):

Оформить заголовок в строке 1 «Численные методы решения нелинейного уравнения».

Оформить заголовок в строке 3 «Шаговый метод».

В ячейки B4 и C4 записать заголовки рядов - соответственно x и F(x).

В ячейки B5 и B6 ввести первые два значения аргумента - 0 и 0,3.

Выделить ячейки B5-B6 и протащить ряд данных до конечного значения (3,3), убедившись в правильном выстраивании арифметической прогрессии.

В ячейку C5 ввести формулу «=B5*B5-4*B5+3».

Скопировать формулу на остальные элементы ряда, используя прием протаскивания. В интервале C5:C16 получен ряд результатов вычисления функции F(x). Видно, что функция дважды меняет знак. Корни уравнения расположены на интервалах [0,9;1,2] и [3;3,3].

Для построения графика зависимости F(x) используем Мастер диаграмм (тип «Точечная», маркеры соединяются гладкими кривыми).

Оформить заголовок в строке 17 «Методы уточнения».

Ввести в ячейку E18 заголовок «Метод половинного деления» (выравнивание по центру).

Ввести в ячейку H18 текст «е=», а в ячейку I18 значение точности «0,001».

В области C19:I19 оформить заголовок таблицы (ряд C - левая граница отрезка «a», ряд D - середина отрезка «x», ряд E - правая граница отрезка «b», ряд F - значение функции на левой границе отрезка «F(a)», ряд G - значение функции на середине отрезка «F(x)», ряд H - произведение «F(a)*F(x)», ряд I - проверка достижения точности «êF(x)ê<е».

Ввести первоначальные значения концов отрезка: в ячейку C20 «0,9», в ячейку E20 «1,2».

Ввести в ячейку D20 формулу «=(C20+E20)/2».

Рис. 5

15. Ввести в ячейку F20 формулу «=C20*C20-4*C20+3».

16. Ввести в ячейку G20 формулу «=D20*D20-4*D20+3».

17. Ввести в ячейку H20 формулу «=F20*G20».

18. Ввести в ячейку I20 формулу «=ЕСЛИ(ABS(G20)<$I$18;²корень²,² ²)».

19. Ввести в ячейку C21 формулу «=ЕСЛИ(H20<0;C20;D20)».

20. Ввести в ячейку E21 формулу «=ЕСЛИ(H20<0;D20;E20)».

21. Скопировать ячейку D20 в ячейку D21, ячейки F20:I20 в ячейки F21:I21.

22. Выделить область C21:I21 и протащить ее по вертикали вплоть до появления в ряду I сообщения «корень» (ячейка I27).

23. Ввести в ячейку C28 заголовок «Метод Ньютона» (выравнивание по левому краю).

24. Ввести в ячейку C29 текст «е=», а в ячейку D29 значение точности «0,000001».

25. Убедиться, что при x=0,9 значение функции и ее второй производной имеют одинаковые знаки.

26. В области B30:E30 оформить заголовок таблицы (ряд B - значение аргумента «x», ряд C - значение функции «F(x)», ряд D - производная функции «F¢(x)», ряд E - проверка достижения точности «êF(x)ê<е».

27. В ячейку B31 ввести первоначальное значение аргумента «0,9».

28. Ввести в ячейку C31 формулу «=B31*B31-4*B31+3».

29. Ввести в ячейку D31 формулу «=2*B31-4».

30. Ввести в ячейку E31 формулу «=ЕСЛИ(ABS(C31)<$D$29;²корень²,² ²)».

31. Ввести в ячейку B32 формулу «=B31-C31/D31».

32. Скопировать ячейки C31:E31 в ячейки C32:E32.

33. Выделить область B32:E32 и протащить ее по вертикали вплоть до появления в ряду E сообщения «корень» (ячейка E34).

34. Ввести в ячейку G28 заголовок «Метод простой итерации» (выравнивание по левому краю).

35. Ввести в ячейку H29 текст «е=», а в ячейку I29 значение точности «0,001».

36. Выбрать функцию j(x), удовлетворяющую условию сходимости. В нашем случае такой функцией является функция S(x)=(x*x+3)/4.

37. В области G30:J30 оформить заголовок таблицы (ряд G - значение аргумента «x», ряд H - значение функции «F(x)», ряд I - значение вспомогательной функции «S(x)», ряд J - проверка достижения точности «êF(x)ê<е».

38. В ячейку G31 ввести первоначальное значение аргумента «0,9».

39. Ввести в ячейку H31 формулу «=G31*G31-4*G31+3».

40. Ввести в ячейку I31 формулу «=(G31*G31 +3)/4».

41. Ввести в ячейку J31 формулу «=ЕСЛИ(ABS(H31)<$I$29;²корень²,² ²)».

42. Ввести в ячейку G32 формулу «=I31».

43. Скопировать ячейки H31:J31 в ячейки H32:J32.

44. Выделить область G32:J32 и протащить ее по вертикали вплоть до появления в ряду J сообщения «корень» (ячейка J39).

45. Выделить ряд x, полученный с помощью метода половинного деления (ячейки D20:D27). Используя Мастер диаграмм, построить зависимость x от номера итерации (тип диаграммы «График»). Определить заголовок ряда «Метод половинного деления».

46. Добавить на график еще два ряда: «Метод Ньютона» - ячейки B31:B34 и «Метод простой итерации» - ячейки G31:G39. Для каждого ряда использовать сою маркировку. График показывает, что наибольшую скорость сходимости имеет метод Ньютона.

47. Ввести в ячейку C57 заголовок «Подбор параметра» (выравнивание по левому краю).

48. Ввести в ячейку C59 текст «x», а в ячейку D59 - «F(x)».

49. Занести в ячейку C60 начальное значение переменной (например, ноль).

50. Ввести в ячейку столбца D60 формулу «=C60*C60-4*C60+3».

51. Дать команду «Сервис» «Подбор параметра».

52. В поле «Установить в ячейке» указать ячейку D60, в которой занесена формула, в поле «Значение» задать 0 (ноль), в поле «Изменяя значение ячейки» указать ячейку C60, где занесено начальное значение переменной.

53. Щелкнуть <ОК> и посмотреть на результат подбора, отображенный в диалоговом окне «Результаты подбора параметра».

54. Нажать <ОК>, чтобы сохранить полученные значения.

55. Повторить расчет п.п. 49-54, задав другое начальное значение в ячейке C60. Совпали ли результаты вычисления?

56. Ввести в ячейку H57 заголовок «Поиск решения» (выравнивание по левому краю).

57. Ввести в ячейку H59 текст «x», а в ячейку I59 - «F(x)».

58. Занести в ячейку H60 начальное значение переменной (например, ноль).

59. Ввести в ячейку столбца I60 формулу «=H60*H60-4*H60+3».

60. Дать команду «Сервис» «Поиск решения».

61. В поле «Установить целевую ячейку» указать ячейку $I$60, в которой занесена формула, в поле «Равной» установить «значению 0», в поле «Изменяя ячейки» указать ячейку $H$60, в поле «Ограничения» установить два ограничения «$H$60>=0,9 и $H$60<=1,2».

62. Нажать кнопку «Выполнить». Появится сообщение, что решение найдено.

63. Нажать кнопку <ОК>, результат будет помещен в рабочий лист.

64. Повторить расчет п.п. 58-63, задав другое начальное значение в ячейке H60. Совпали ли результаты вычисления?

2.7. Задача максимизации прибыли предприятия

Одной из распространенных экономических задач является задача макси­мизации прибыли предприятия. Известно, что балансовая прибыль есть разница между выручкой и затратами на производство продукции P=N-Z. В общем слу­чае выручка от реализации продукции может быть представлена полиномом 2-й степени от количества продукции N=a₀Q+a₁Q². Нелиней­ность может быть связана с тем, что в условиях монополии цена единицы про­дукции k может уменьшаться с ростом количества выпущенной продукции Q:

k=a₀+a₁Q (a₀>0, a₁<0). В свою очередь, функция затрат может быть представ­лена полиномом 3-й степени Z=b₀+b₁Q+b₂Q² +b₃Q³. Кубическая нелинейность может объясняться тем, что при производстве малой партии товаров издержки быстро растут, затем с ростом Q темп роста издержек уменьшается, но по дос­тижении некоторого критического значения Q начинает работать «закон убы­вающей отдачи», в соответствии с которым издержки вновь начинают расти ус­коренными темпами. Прибыль максимальна, когда dP/dQ = 0. С помощью паке­та Excel решим данную задачу, полагая заданными коэффициенты: b₀ = 10, b₁=1, b₂= -0.1, b₃ = 0.01, a₀= 5, a₁= -0.1.

Последовательность действий при реализации в пакете Excel (рис. 6):

1. Оформить заголовок в строке 1 «Максимизация прибыли».

2. В ячейки A3, ВЗ, СЗ, D3 и ЕЗ записать заголовки рядов - соответственно Q, N, Z, P, и dP/dQ.

3. В ячейки F3, F4, F5, F6, F9, F10 записатьназвания коэффициентов- со­ответственно b₀, b₁, b₂, b₃, a₀, a₁.

4. В ячейки G3, G4, G5, G6, G9, G10 записать значения коэффициентов -соответственно 10; 1; -0,1; 0,01; 5; -0,1.

5. В ячейку Н5 ввести текст «Издержки Z=b0+bl*Q+b2*Q^2+b3*Q^{^}3»

6. В ячейку Н6 ввести текст «Выручка N=a0*Q+a1*Q^2»

7. В ячейку Н7 ввести текст «Прибыль P=N-Z»

8. В ячейки А4 и А5 ввести первые два значения аргумента - 0 и 1.

9. Выделить ячейки А4-А5 и протащить ряд данных до конечного значения

(21), убедившись в правильном выстраивании арифметической прогрессии. 10. В ячейку В4 ввести формулу «=A4*$G$9+A4*A4*$G$10».

11. Скопировать формулу на остальные элементы ряда, используя прием протаскивания. В интервале В4:В25 получен ряд результатов вычисления вы­ручки N(Q).

12. В ячейку С4 ввести формулу «=$G$3+A4*$G$4+A4*A4*$G$5+A4*A4*A4* $G$6».

13. Скопировать формулу на остальные элементы ряда, используя прием протаскивания. В интервале С4:С25 получен ряд результатов вычисления из­держек Z(Q).

14.В ячейку D4 ввести формулу «=B4-C4».

15. Скопировать формулу на остальные элементы ряда, используя прием протаскивания. В интервале D4:D25 получен ряд результатов вычисления при­были P(Q).

16. В ячейку Е4 ввести формулу «=($G$9-$G$4)+2*($G$10-$G$5)*A4-3*$G$6* А4*А4».

17. Скопировать формулу на остальные элементы ряда, используя прием протаскивания. В интервале Е4:Е25 получен ряд результатов вычисления dP/dQ для различных значений Q.

18. Построить на одной диаграмме графики зависимостей N(Q), Z(Q) и P(Q), ис­пользуя соответствующие ряды данных.

19. Построить на отдельной диаграмме зависимость dP/dQ от Q. Точка пересе­чения графика с осью абсцисс дает значение Q, соответствующее макси­мальной прибыли (шаговый метод).

Рис.6