MLoop 2

Задача. Используйте метод хорд для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] все действительные корни уравнения  [latex]\frac{x}{2 \cdot \sin x +1}=\tan(\ln(x^2+1))[/latex].  Для подготовки необходимых графиков воспользуйтесь этим ресурсом.

Тесты(найдено с помощью математической системы WolframAlpha):

[latex]A[/latex] [latex]B[/latex] [latex]x\approx[/latex]
-20 20  -11.6945378230838209122818536587051434153…


-1.25741503276862309237205903178504130394…

0


0.547316310185252929580383582338832450320…

10.9948442206261587135425985750810372810…

Код программы

 

Алгоритм

Для начала запишем данное нам уравнение в виде функции [latex]y=f(x)[/latex] и построим ее график:

[latex]y=\frac{x}{2 \cdot sin x +1}-tan(ln(x^2+1))[/latex]

 

save (4)

Задача о нахождении приближённых значений действительных корней уравнения [latex]f(x)=0[/latex] предусматривает предварительное отделение корня, то есть установление интервала, в котором других корней данного уравнения нет.

Метод хорд предусматривает замену функции на интервале на секущую, и поиск ее пересечения с осью [latex]OX[/latex]. На заданном интервале [latex][a,b][/latex] с точностью [latex]\varepsilon[/latex] корень будет вычисляться согласно итерационному выражению, которое имеет вид:

[latex]x_{i+1}=x_{i-1}-\frac{f(x_{i-1}) \cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1}) ) }[/latex]

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

  1. В точке, где находится предполагаемый корень, имеется разрыв второго рода. Здесь метод хорд обнаруживает перемену знака и начинает сужать отрезок. Однако расстояние между крайними точками  отрезка не уменьшается, а увеличивается. А именно увеличивается проекция отрезка на ось [latex]OY[/latex]. И чем ближе мы находимся к точке разрыва, тем она больше, а в самой точке стремится к бесконечности. В качестве примера приведем функцию [latex]\frac{(x-5)^2}{x-4}[/latex], имеющую разрыв второго рода в точке [latex]x=4[/latex].
    save

  2. Аналогичный случай — точка разрыва первого рода, где наша хорда стремится к некоторой константе — величине разрыва. Пример — функция [latex]\frac{\sin x\cdot(x-2.5)}{\left | x-2,5 \right |}[/latex], имеющая разрыв первого рода в точке [latex]x=2,5[/latex].
    save (1)

  3. Функция не является разрывной и даже имеет корень, однако в точке корня производная стремится к бесконечности. Например, функция [latex]\sqrt[3]{x-1,2}[/latex], имеющая корень в точке [latex]x=1,2[/latex]. Для функций подобного рода длина проекции отрезка на ось [latex]OY[/latex] будет очень медленно меняться, вследствие чего для разумного числа итераций она будет превосходить заранее выбранную точность [latex]\varepsilon[/latex].

save (2)

  1. Функция равна нулю или очень близка к нулю на некотором интервале(например, функция [latex]y=rect(x-1,5)\cdot(x-1)\cdot(x-2)^2[/latex]). Здесь метод хорд найдет пересечение с осью [latex]OX[/latex]  в интервале, где находятся корни(одна из сторон отрезка будет корнем), но все последующие итерации будут выдавать эту же точку. Поэтому хорда не будет уменьшаться, и даже этот один корень не будет найден(если будет использоваться стандартная [latex]\delta[/latex]-оценка точности по оси [latex]OX[/latex]).

save (3)

  1. Функция вида [latex]y=x^{2k}[/latex] или ей подобная, например, [latex]y=1+\sin x[/latex], к которой метод хорд вообще не применим, так как нарушается начальное условие применимости этого метода. Здесь нужно ввести дополнительную проверку. Изменим значение функции на небольшую константу — нашу точность [latex]\varepsilon[/latex] и повторим процедуру поиска корней. В результате мы получим [latex]2k[/latex] корней, каждую пару из которых мы можем считать краями интервала, в котором лежит настоящий корень.

save (6)

К счастью, в данной нам функции присутствует только один из этих случаев, а именно разрыв второго рода. Аналитически рассмотрев нашу функцию, мы обнаружили, что корни следует искать в окрестности точек[latex]\sqrt{e^{\frac{\pi}{2}+\pi \cdot k}-1}[/latex] с отклонением [latex]\pm\pi[/latex]. В корнях функции ее производная быстро растет с ростом [latex]k[/latex].

Критерием отбрасывания кандидата на корень будет рост длины хорды при сужении интервала. Критерием останова будет сужение интервала до заданной точности [latex]\delta[/latex].
Код программы

Ю11.16

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex]
где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:
процесс сходится
Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex] [latex]A[/latex] [latex]A^{-1}[/latex] Результат
3 1 2 3
5 5 7
11 13 7
-0.964771 0.430661 -0.017183
0.723533 -0.447973 0.137884
0.172358 0.155200 -0.086211
Пройден
2 1 2
2 1
-0.333067 0.666400
0.666400 -0.333067
Пройден
5 1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
Пройден
3 1 2 3
4 5 6
7 8 9
Матрица вырождена Пройден

Программный код:

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

Алгоритм решения
При решении данной задачи оправдывает себя подход «разделяй и властвуй»: вычисление обратной матрицы подразумевает промежуточные этапы, корректной реализации которых следует уделить особое внимание. Наверняка стоило бы написать класс matrix и реализовать перегрузку операций, но задачу можно решить и без применения объектно-ориентированных средств, пусть от этого решение и потеряет в изящности.
Можно выделить следующие подзадачи:

  1. Инициализация динамического двухмерного массива и передача его в функцию.
  2. Вычисление определителя матрицы (с применением метода Гаусса).
  3. Вычисление нормы матрицы.
  4. Транспонирование матрицы.
  5. Умножение матрицы на скаляр.
  6. Матричное умножение матриц.
  7. Сложение двух матриц.
  8. Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

  • Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
  • Вычисление определителя можно разбить на два последовательных шага:
    1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
    2. Вычисление определителя как произведения элементов главной диагонали.
    3. Если матрица вырождена, то дальнейшие вычисления не производятся.

  • Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
  • При транспонировании обмениваются местами элементы, симметричные главной диагонали.
  • При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
  • При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
  • Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
  • Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().