Блочно-линеаризационный подход к решению систем нелинейных уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА 1. Описание подхода и исследование сходимости алгоритмов БЛП

§ 1.1. Основные конструкции метода.

§ 1.2. Структурная классификация алгоритмов решения систем нелинейных уравнений и задач безусловной минимизации.

§ 1.3. Исследование сходимости алгоритмов БЛП для решения систем нелинейных уравнений.

ГЛАВА 2. Анализ сходимости и устойчивости алгоритмов БЛП

§ 2.1. О скорости сходимости алгоритмов БЛП.

§ 2.2. Исследование устойчивости алгоритмов, построенных на основе блочно-линеаризационного подхода.

§ 2.3. Анализ устойчивости методов решения систем нелинейных уравнений и задач безусловной минимизации.

ГЛАВА 3. Методика и примеры реализации алгоритмов на основе блочно-линеаризационного подхода

§3.1. Методика построения алгоритмов БЛП.

§ 3.2. Методы решения систем нелинейных уравнений.

3.2.1. Блочный вариант метода сопряженных невязок (МСН) (Алгоритм А1 (/</<«)).

3.2.2. Блочный симметричный вариант метода сопряженных невязок (Алгоритм А2 (1 <1 <п)).

3.2.3. Модифицированные варианты метода сопряженных градиентов (Алгоритм АЗ (2 <1 <п ; т 1 = 1, т^=2,1 = 2Г1)).

§ 3.3. Методы решения задач безусловной минимизации.

3.3.1. Блочный вариант метода сопряженных градиентов (Алгоритм В1 (1 <1 <п)).

3.3.2. Модифицированный метод сопряженных градиентов (Алгоритм В2 (2 <1 <п; т[1] = 1, т[1[ = 2,

1 = ^7)).

3.3.3. Блочный вариант метода минимальных итераций (Алгоритм ВЗ (7 <1<п)).

3.3.4. Блочный вариант квазиньютоновских методов (АлгоритмВ4 (1 <1 <п)).

Большое число теоретических и прикладных задач вычислительной математики, математического программирования, оптимального управления и других разделов прикладной математики сводится к численному решению двух тесно связанных задач: систем нелинейных уравнений (СНУ) и безусловной минимизации (БМ). В этой связи разработка эффективных методов решения СНУ и задачи БМ является актуальной проблемой, имеющей не только теоретическое, но и большое практическое значение.

Формулировка этих задач следующая:

Задача СНУ. Найти некоторую точку х*, являющуюся решением системы нелинейных уравнений: р(х) = 0, где (р:Яп-+Яп. (0.1)

Задача БМ. Найти точку локального минимума х* = агё тт /(х), где /: Яп Я1. (0.2) хеЯ"

В дальнейшем через х* и X* будем обозначать, соответственно, решение и множество решений этих задач. При этом предполагается, что функции ф(х) и /(х) достаточно гладкие и решения указанных задач существуют. Процесс решения систем нелинейных уравнений и задач безусловной минимизации обычно итерационный, т.е. решение х* ищется как предел последовательности точек {хк}: хк =хк! +Хк рк, рк еЯп, Хк &Я1, к = 1,2,3,., которая генерируется конкретным методом решения, начиная с некоторой точки х0. В случае неединственности решения предельная точка х* зависит от выбора начальной точки х0. Точке х0 для систем нелинейных уравнений и задач безусловной минимизации соответствует так называемое множество уровня (множество Лебега):

Х={хЕ^":|ф(л:|<|ф(х0|}, (0.3)

Х = :/(*)</(х0)}, (0.4) при этом допустимым множеством или областью определения для рассматриваемых задач можно считать не все пространство Я" , а множество Х^Яп : р:ХаЯп ->Яп и/:ХаЯп Я1 (0.5)

Отметим взаимосвязь СНУ и задач БМ. Задача БМ является частным случаем задачи СНУ в том смысле, что решение первой есть решение второй, где ф(х) = У/(х). И, наоборот; для невырожденной матрицы ф'(х), х е X, задача СНУ эквивалентна, например, задаче БМ с минимизируемой функцией Р{х)= — ||ф(х))| . В связи с этим, процесс решения СНУ можно интерпретировать как процесс решения задачи БМ, а процесс решения задачи БМ - интерпретировать как процесс решения СНУ. В настоящей работе предлагается некоторый подход для построения как методов решения систем нелинейных уравнений, так и методов решения задач безусловной минимизации, при этом в процессе анализа численных методов учитывается их специфика.

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

Актуальность работы. К настоящему времени можно констатировать, что теория численных методов решения указанных задач является достаточно глубоко разработанной, им посвящено значительное число работ [1-И2].

Однако, как отмечает ряд авторов [2], [7], [10], [12], теоретически доказанная высокая скорость сходимости (сверхлинейная или квадратичная) методов решения рассматриваемых задач не гарантирует эффективности их практического использования при решении различных классов задач, как например, плохо обусловленных задач, задач большой размерности и т.д. Под эффективностью обычно понимается получение решения с требуемой точностью за приемлемое время, при условии рационального использования вычислительных ресурсов ЭВМ, то есть оперативной памяти и времени решения задач. Следует заметить, что в настоящее время проблема экономии памяти ЭВМ потеряла свою актуальность в связи с огромными достижениями научно-технического прогресса в области вычислительной техники.

В связи со сказанным, можно привести такое определение эффективности алгоритма:

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

Однако, это определение достаточно расплывчато и не конкретно. Чаще рассматривают сравнительную эффективность численных методов (алгоритмов), то есть:

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

Следует отметить, что эффективность метода зависит от многих причин. Выделим две из них:

1. Во-первых - это свойства сходимости основной (теоретической) схемы метода, которую можно также назвать невозмущенной схемой.

2. И второе - способы численной реализации основной, невозмущенной схемы.

Обсудим эти понятия.

Основные схемы могут отличаться теоретической скоростью сходимости, как, например, метод Ньютона для решения задачи (0.1) имеет квадратичную скорость сходимости; для задачи (0.2) метод Ньютона также обладает квадратичной скоростью сходимости; метод наискорейшего спуска для сильно выпуклых функций имеет линейную скоростью сходимости; метод сопряженных градиентов Флетчера-Ривса - квадратичная скорость сходимости; другие варианты методов могут обладать сверхлинейной скоростью сходимости. Скорость сходимости метода при этом зависит и от исследуемого класса функций.

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

На практике достаточно часто встречаются неустойчивые задачи и задачи большой размерности, для решения которых требуется значительное время. При этом, причиной неэффективности алгоритмов решения задач являются погрешности Арк, АХк определения вектора рк (в первую очередь) и шага Хк (во вторую). На величину погрешности Арк влияет схема реализации численного метода и объем вычислений вектора рк, которые в свою очередь зависят от размерности и устойчивости (обусловленности) решаемой задачи.

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

Цель работы. Целью настоящей работы является:

1. Разработка подхода, позволяющего строить широкий класс численных методов решения СНУ и задач БМ, включающий методы, обладающие высокой теоретической и реальной скоростью сходимости.

2. Построение схемы исследования устойчивости итерационного процесса для широкого класса методов решения СНУ и задач БМ при наличии вычислительных погрешностей.

3. Исследование сходимости предлагаемых итерационных методов решения СНУ и задач БМ.

Научная новизна.

1. В диссертационной работе предложен подход к построению численных методов решения систем нелинейных уравнений и задач безусловной минимизации. В основе подхода лежит общая методология переноса численных методов линейной алгебры для решения рассматриваемых нелинейных задач. Эта методология позволяет получать не только известные методы решения СНУ и задач БМ, но и новые высокоэффективные методы.

2. На основе этого подхода предложены новые методы решения СНУ и задач БМ, реальная скорость сходимости которых не ниже, чем у известных методов решения указанных задач.

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

Практическая ценность. Численные методы, предложенные в диссертации, применимы для широкого круга прикладных задач, связанных с решением СНУ и задачи БМ.

1. Для проверки реальной эффективности предложенных методов решения систем нелинейных уравнений и задач безусловной минимизации были разработаны пакеты программ на языке Фортран (.Microsoft Fortran PowerStation 4.0) для персонального компьютера Pentium II {Intel Celeron 400/64Mb).

2. Особенностью предложенных методов является возможность построения многочисленных схем вычисления вектора рк, позволяющих строить гибкие вычислительные процессы решения указанных задач. При помощи таких схем были построены методы решения систем нелинейных уравнений и задач безусловной минимизации не менее эффективные по времени решения, чем метод Ньютона и другие известные методы. Эффективность по времени решения некоторых предложенных методов возрастает при увеличении размерности задач.

Публикации. Основное содержание настоящей работы опубликовано автором в статьях [15], [25], [28], [38].

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

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие основные результаты:

1. Предложен блочно-линеаризационный подход к решению систем нелинейных уравнений и задач безусловной минимизации. Идея подхода заключается в разбиении последовательности точек {х^}, к = 1,2,., сходящейся к решению х , на связанные между собой группы (блоки) точек и определении в каждой точке последовательности вектора направления рк, как приближенного решения линеаризованной системы для нелинейного уравнения ф(х)=6>, <р:Яп Яп, (или У/(х)=0 для задачи БМ) на некотором линейном в Яп многообразии. Базисные векторы линейного многообразия могут выбираться многими способами, но наиболее конструктивным подходом в их определении является применение различных классов методов решения систем линейных уравнений. При этом для реализации численных методов решения СНУ и задач БМ широко применяются разностные аппроксимации производных функций ф(х) и /(х) специального вида. Шаг Хк е Я1 вдоль направления рк можно выбирать различными способами, но основной исследуемый в диссертации способ выбора шага Хк - это минимизация функции ||ф(хА; +Хрк)|| по параметру X для решения СНУ, и для решения задачи БМ - минимизация по параметру X функции /(хк! +Хрк).

2. На основе БЛП решения СНУ и задач БМ была предложена структурная классификация методов решения указанных задач. В работе показано, что многие известные методы решения систем нелинейных уравнений и задач безусловной минимизации характеризуются определенными структурными параметрами, совпадающими или не совпадающими с параметрами БЛП, при этом одной из основных характеристик методов является параметр блочности метода.

3. Изучены общие свойства сходимости методов решения СНУ и задач БМ, построенных на основе БЛП. Доказана сходимость указанных методов к решению х* исследуемых задач, а также, при некоторых дополнительных условиях, линейная скорость сходимости обширного класса предложенных методов.

4. Разработана методика исследования устойчивости предложенного класса методов при наличии погрешностей в вычислении вектора направления поиска и длины шага вдоль этого направления.

5. На основе БЛП построены новые методы решения СНУ и задач БМ. Исследованы следующие новые методы:

А) Для решения СНУ:

• Когда матрица Якоби ф'(х) несимметрична, предложен блочный вариант метода сопряженных невязок, причем при параметре блочности 1 = 1 метод называется дискретный ш-шаговый метод сопряженных невязок;

• Когда матрица Якоби ф'(х) симметрична, предлагаются следующие методы решения СНУ: блочный симметричный вариант метода сопряженных невязок, причем при параметре блочности 1 = 1 метод называется симметричный вариант дискретного га-шагового метода сопряженных невязок;

• Также для симметричной матрицы Якоби ф'(х) предложены модификации метода сопряженных градиентов для решения систем нелинейных уравнений ф(х) = 0, при этом параметр блочности / < п, размерность базисных подпространств т = 2.

Б) Для решения задачи БМ предложены следующие методы:

• Блочный вариант метода сопряженных градиентов при блочности 1<1<п\

• Две модификации метода сопряженных градиентов при параметре блочности / < п и размерности базисных подпространств т = 2;

• Блочный вариант метода минимальных итераций при блочности 1<1<п\

• Блочный вариант квазиньютоновских методов при блочности 1<1<п.

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

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

7. Предложенные методы решения СНУ и задач БМ реализованы в пакетах программ на языке Фортран {Microsoft Fortran PowerStation 4.0) для персонального компьютера Pentium {Intel Celeron 400/64Mb). Рассмотренные методы показали высокую эффективность при решении различных классов тестовых задач, причем их эффективность часто не уступает эффективности широко применяемых на практике численных методов решения систем нелинейных уравнений и задач безусловной минимизации.

1. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. - М.: Наука, 1975

2. Пшеничный Б.М., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975

3. Карманов В.Г. Математическое программирование. М.: Физматлит, 2000

4. Иванов В.В. Методы вычисления на ЭВМ. Справочное пособие. Киев: Наукова думка, 1986

5. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982

6. Островский А. Решение уравнений и систем уравнений. М.: ИЛ, 1963

7. Химмелъблау Д. Прикладное нелинейное программирование. М.: Мир, 1975

8. Adams L., Nazareth J.L. edit. Linear and Nonlinear Conjugate Gradient-Related Methods. SIAM, Philadelfia, 1996

9. Абаффи Й., Спедикато Э. Математические методы для линейных и нелинейных уравнений. М.: Мир, 1996

10. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983

11. Бахвалов Н. С. Численные методы. Т. 1. М.: Наука, 1973

12. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985

13. Бирюков А.Г. Об одном подходе к решению задач безусловной минимизации. В сб.: Тр. МФТИ. Серия: Аэрофизика и прикладная математика. Долгопрудный, 1979, с. 188-192

14. Бирюков А.Г. Блочно-квадратичный подход для решения задач безусловной минимизации. В сб.: Тр. МФТИ. Серия: Аэрофизика и прикладная математика. Долгопрудный, 1980, с. 83-86

15. Бирюков А.Г., Седелъникова А.В. Блочно-линеаризационный подход к решению систем нелинейных уравнений. Междуведомственный сборник: Моделирование процессов управления и обработки информации. МФТИ. Москва, 1994, с. 225-230

16. Деннис Дж., Шнабелъ Р. Численные методы безусловной минимизации и решения нелинейных уравнений. М.: Мир, 1988

17. Аоки М. Введение в методы оптимизации. М.: Наука, 1977

18. Бирюков А.Г. Об устойчивости методов безусловной минимизации. -Междуведомственный сборник: Математические методы управления и обработки информации. МФТИ. Москва, 1982, с. 26-31

19. Бирюков А.Г. Разностно-аппроксимационный подход к решению задач безусловной минимизации и систем нелинейных уравнений. Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Долгопрудный, 1988

20. Бурдаков О.П. Влияние точности вычислений на сходимость модифицированного метода Ньютона в задаче поиска седловых точек. В сб.: Тр. МФТИ. Серия: Аэрофизика и прикладная математика. Долгопрудный, 1979, с. 184-187

21. Dembo R.S., Eisenstat S.C., Steihand Т. Inexact Newton Methods. SIAM J. Numer. Anal., 1982, Vol. 19, № 2, pp. 400-408

22. Ipma T.I. Local Convergance of Inexact Newton Methods. SIAM J. Numer. Anal, 1984, Vol. 21, № 3, pp. 583-590

23. Woznakowski H. Numerical Stability for Solving Nonlinear Equations. -Numer. Math, 1977, Vol. 27, pp. 373-390

24. Ipma T.I. The Effect of Rounding Errors on Newton-like Methods. JMA Jour, of Numer. Anal, 1983, Vol. 3, pp. 109-118

25. Седелышкова A.B. Численные методы решения систем нелинейных уравнений на основе блочно-линеаризационного подхода. Междуведомственный сборник: Моделирование процессов управления и обработки информации. МФТИ. Москва, 1996, с. 118-123

26. Воеводин В.В. Линейная алгебра. М.: Наука, 1980

27. Elman Н.С. Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations. Report No.229, Computer Science Department, Yale University

28. Седелъникова A.B. Численные методы решения задач безусловной минимизации на основе блочно-линеаризационного подхода. Междуведомственный сборник: Моделирование управляемых динамических систем. МФТИ. Москва, 1997, с. 109-114

29. Stifel E.L. Relaxationsmethoden bester strategie zar losung linearer gleichangssystems. Comment. Math. Helv. 29, 1955, pp. 159-179

30. Полак Э. Численные методы оптимизации. М.: Мир, 1974

31. Поляк Б. Т. Методы сопряженных градиентов в задачах на экстремум. -М.:ЖВМ, т. 9, №4, 1969

32. Broyden C.G. Block Conjugate Gradient Methods. Optimization Methods and Software, 1993, Vol. 2, pp. 1-17

33. Byrd R., Nocedal J., Zhu C. Towards a Discrete Newton Method with Memory for Large-scale Optimization. Nonlinear Optimization and Applications, 15.02.1996 Technical Report OTC 95/01

34. Nocedal J. Large-scale Unconstrained Optimization. 23.06.1996 Technical Report, Department of Electrical Engineering Since, Northwestern University

35. Бирюков А.Г. О разностно-аппромаксимационном подходе к решению систем нелинейных уравнений. ДАН, 1983, т. 240, № 4, с. 777-781

36. Фаддеев Д.К., Фаддеееа В.Н. Вычислительные методы линейной алгебры. M.-JI: Физматгиз, 1960

37. Бирюков А.Г. Блочный вариант квазиньютоновских методов. В сб.: Математические методы управления и обработки информации. Москва, 1984, с. 31-34

38. Седелъникова А.В. О сходимости численных методов решения систем нелинейных уравнений на основе блочно-линеаризационного подхода. -Междуведомственный сборник: Моделирование управляемых динамических систем. МФТИ. Москва, 1997, с. 115-120

39. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984

40. Бирюков А.Г. Систематизация вычислительных процедур типа Грама-Шмидта для решения систем линейных уравнений. Междуведомственный сборник: Моделирование процессов управления и обработки информации. Москва, 1999, с. 242-252

41. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977

42. Годунов С.К Решение систем линейных уравнений. Новосибирск: Наука, Сиб.отделение, 1980

43. Икрамов Х.Д. Численные методы для симметричных линейных систем. М.: Наука, 1988

44. Парлетт Б. Симметричная проблема собственных значений. Численные методы. М.: Мир, 1983

45. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. Мир.: Мир, 1969

46. Аттетнов А.В., Галкин С.В., Зарубин B.C. Методы оптимизации. М.: МГТУ им. Н.Э.Баумана, 2001

47. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986

48. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. М.: МАИ, 1998

49. Birjukov A.G. Software for Regional Studies: on the Difference-Approximation Approach to Solving Systems of Nonlinear Equations. -JJASA, 1993, pp. 82-88, Laxenburg, Austria

50. Hestenes M.R. Conjugate Directions Methods in Optimization. N.Y.: Springer-Verlay, 1980

51. Хорн P., Джонсон У. Матричный анализ. М.: Мир, 1989

52. Уилкинсон Д.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970

53. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988146

54. Brown K.M. Solutions of Simultaneous Nonlinear Equations. Comm. ACM, 1967, Vol. 10, pp. 728-729

55. Данилин Ю.М. Методы сопряженных направлений, не требующие решения одномерных задач минимизации. ДАН, 1974, т. 213, № 3, с. 513516

56. Буланый А.П., Данилин Ю.М. Квазиньютоновские алгоритмы минимизации, основанные на построении систем сопряженных векторов. ЖВМ и МФ, 1983,т. 18, № 4, с. 877-885

57. More J.J., Wright S.J. Optimization Software Guide. SIAM, Philadelfia, 1993

58. Nash S.G. A Survey of Trancated-Newton Methods. Jour, of Comput. and Applied Math., 124, 2000, pp. 45-59

59. Martinez J.M. Practical Quasi-Newton Methods for Solving Nonlinear Systems. Jour, of Comput. and Applied Math., 124, 2000, pp. 97-121

60. Weiss R., Podgajezki I. Overview on New Solvers for Nonlinear Systems. -Applied Numerical Math., 30, 1999, pp. 379-391

61. Анализ эффективности методов решениясистем нелинейных уравнений (результаты численного эксперимента)

62. В качестве тестовых систем нелинейных уравнений использовались следующие системы:

63. А). 2а ■ ip • x¡ + ¿(х ■ + cos x¡ ■ sinx ■) = 0, i = 1,n¡, n¡ <n\j=n¡ + l2a • jp -Xj +cos Xj -sinx^)=0, j = n¡ + l,n. (П1.1)I

64. Параметры a>0, p = 0,1,2,.

65. Система нелинейных уравнений (П1.1) имеет симметричную матрицу-

66. Якоби, ее решение x¡ = 0, i = 1,п.\ п~! 0,5 -п-уп 1)-х п - ^t-xf1. Б). 2-(xj-l)-2-a-j-p-xp~1а • пп-1\0,5-п-(п-l)-xп -^t-xft=iп-1t=l

67. О, j = 7,п-1; = 0,j = n. (П1.2)

68. Параметры а > 0, р = 1,2,3,.

69. Матрица Якоби симметричная. Решение х ■ = 1, j = 1,п - единственная точка.1. В), х/ +а-^х2/ =0, i = l;j=2x2t + р/ • + Ji ■ х2пР 0, i = Хп. (П1.3)

70. Параметры системы а> 0, (Зг >0, у. >0, i = 2,п, р = 1,2,3,.

71. Параметры а, (Зг-, у; различны, например, а = 0,01; 0,1; 7,2 23 г = 7 = const; Р {=i;2i и т.д. i = 2,n, у г- =0,7; 7 = const', у ¡=i ;2i и т.д.i = 2, п.

72. Решение х* =0, i = 1,п единственная точка.

73. Матрица Якоби несимметрична и вырожденна в точке х* = 0

74. Г), (l-xj)2 +а^{хн-х.)2 =0, i = l;j=21 xt Y + p,. • (1 - xn, )2p + Yi • (7 - X n)2p=0, i = . (П1.4)

75. Параметры системы a> О, Рг >0, y( >0, i = 2,n, p = 1,2,3,. Параметры a, Рг, yi различны, как и в системе В). Решение х * = 7, i = 1,п - единственная точка.

76. МатрицаЯкоби несимметрична и вырожденна в точке хг = 7, / = 1,п.

77. Как видно из рисунка 1 при / > 8 эффективность алгоритма А1 становится хуже, чем у метода Ньютона, а при 1 = 1 эффективность этих методов примерно одинакова. В связи с этим, рассмотрим эффективность алгоритма