Поиск более одного корня с алгоритмами поиска корней

Question

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

Например: y = x^2

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

Одна вещь, чтобы отметить, что уравнения не были бы ваши типичные полиномы, но может быть что-то такое, как ln(x^2) + x - 15 = 0

Что такое корень поиска алгоритм, который мог бы решить для этого, или как можно отредактировать алгоритм поиска корней, такой как метод Bisection/Newton/Brent для решения этой проблемы, (полагая, что я прав в том, что метод Ньютона и Брента может решить только один корень).

Answer 1

Я бы сказал, что нет общего метода для поиска всех корней общего уравнения. Тем не менее, можно попытаться разработать методологии, как только будут указаны достаточные условия. Даже простые квадратичные уравнения ax + bx + c = 0 не являются полностью тривиальными, поскольку существование вещественных корней зависит от знака b -4ac, что не сразу становится очевидным. Таким образом, есть много методов, чтобы применить, например Newton-Raphson, но не общий метод для общего случая, особенно для уравнений типа Ln (х) + х-15 не = 0.

Answer 2

Итог: Вы должны изолировать корни сами.

Информация зависит от алгоритма: Если вы используете метод биссекции или Брент, вам нужно создать набор интервалов, каждый из которых содержит уникальный корень. Если вы используете метод Ньютона, вам нужно придумать набор исходных оценок (поскольку он сходится к корню с учетом начальной точки и с разными начальными точками он может или не может сходиться к различным корням).

Answer 3

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

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

Итак, учитывая приличную схему поиска корней, вы можете попробовать простые вещи, такие как дефляция. Таким образом, рассмотрим простую функцию, такую ​​как функция Бесселя первого рода. Я буду использовать все мои примеры с помощью MATLAB, но для любого инструмента, который имеет стабильный хорошо написанный корневой инструмент, такой как fzero в MATLAB, будет достаточно.

ezplot(@(x) besselj(0,x),[0,10]) 
grid on 

f0 = @(x) besselj(0,x); 
xroots(1) = fzero(f0,1) 
xroots = 
    2.4048 

Из графика мы можем видеть, что есть второй корень около 5 или 6.

Теперь отпустите f0 для этого корня, создав новую функцию, основанную на f0, но ту, которая не имеет корня в xroots (1).

f1 = @(x) f0(x)./(x-xroots(1)); 
ezplot(f1,[0,10]) 
grid on 

Обратите внимание, что в этой кривой, корень f0 в xroots (1) теперь всесильный прочь, как будто его не существует. Можем ли мы найти второй корень?

xroots(2) = fzero(f1,2) 
xroots = 
    2.4048 5.5201 

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

Лучшей схемой может быть (для 1-й проблемы) использовать схему брекетинга, объединенную с методологией выборки. Я говорю лучше, потому что не требует модификации начальной функции для сдувания корней. (Для 2-d или выше, все становится гораздо более волосатым, конечно.)

xlist = (0:1:10)'; 
flist = f0(xlist); 

[xlist,flist] 
ans = 
     0 1.0000 
    1.0000 0.7652 
    2.0000 0.2239 
    3.0000 -0.2601 
    4.0000 -0.3971 
    5.0000 -0.1776 
    6.0000 0.1506 
    7.0000 0.3001 
    8.0000 0.1717 
    9.0000 -0.0903 
    10.0000 -0.2459 

Как вы можете видеть, функция имеет знак изменения в интервалах [2,3], [5,6], и [8,9]. Здесь будет работать корень, который может искать в скобке.

fzero(f0,[2,3]) 
ans = 
    2.4048 

fzero(f0,[5,6]) 
ans = 
    5.5201 

fzero(f0,[8,9]) 
ans = 
    8.6537 

Просто найдите изменения знака, затем бросьте известную скобку в корневой искатель. Это даст столько решений, сколько вы можете найти в скобках.

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

Например, рассмотрим функцию f (x) = x^2-x, которая имеет одиночные корни в 0 и в точке 1. Но если вы отбираете эту функцию в -1 и 2, вы обнаружите, что она положительна в обоих точках. Нет никаких изменений знака, но есть два корня.

Опять же, метод NO может быть выполнен идеально. Вы можете ВСЕГДА разработать функцию, которая приведет к сбою любого такого числового метода.