다항식 근점 찾기 이분법

Question

이항법을 사용하여 다항식의 근원을 찾고, 경우에 따라 다항식에 따라 뿌리가 음수이거나 양수일 수 있습니다.

다항식을 계산 한 결과에 따라 뿌리가 음수인지 아니면 양수인지를 판단 할 수 있다는 것을 이해합니다 ... 그러나 x로 사용하는 것이 확실하지 않습니다.

누구나 통찰력을 줄 수 있습니까?

Answer 1

뿌리가 음수 또는 양수 일 수 있다는 사실은 이분법과 아무 관련이 없습니다. 미적분에서 intermediate value theorem을 사용하여 뿌리의 존재를 증명할 수 있습니다.

x1 및 x2은 y(x1)이 음수이고 y(x2)은 양수입니다. 그런 다음 IVT에서 x1과 x2 사이에 루트가 있다는 것을 알고 있습니다. 그 간격에서 이진 검색을하면됩니다. y(x3) = y((x1+x2)/2)이 음수이면 [x3,x2] 간격으로 이분 검색을 반복합니다. 그렇지 않으면 양수인 경우 [x1,x3] 간격으로 검색하십시오.

루트가 음수인지 양수인지는 중요하지 않습니다. 그 질문에 대한 대답이 확실하지 않지만 알고리즘을 이해하는 데 도움이되기를 바랍니다.

Answer 2

많은 루트 파인더를 사용하면 사용자가 시작점을 지정하여 검색을 시작할 수 있습니다. 이를 통해 사용자는 결과를 "바이올린 (fiddle)"하여 다른 뿌리를 찾거나 파인더가 루트에 수렴되도록 할 수 있습니다.

는 사용자가 포인트의 소수를 프로빙으로 시작 할 수 시작 값을 제공 할 수 있도록 이해가되지 않는 경우 :

-1

, 0, 1
• -10, 0, 10
• -100, 0 등

입력 다항식이 홀수 인 경우

(100)이 결국 이등분하는 적절한 범위를 발견 할 것이다. 입력이 짝수 다항식이라면, 부호 변화를 결코 포착하지 못할 수도 있습니다 (f (x) = x^2 - 결코 음수가 아닙니다). 그래서 특정 (설정 가능한?) 양의 프로빙 후에 포기 할 준비를하십시오.

여기 10의 제곱으로 범위를 더 크게 만들 것을 제안했습니다. 이분법 접근법은 매번 절반으로 범위를 줄이기 때문에 이것은 아마도 너무 보수적입니다. (그것은 다음 "엄격한"브래킷의 범위를 줄이기 위해 양분의 두 세 번 반복 사이에 걸릴 수 있습니다.) 아마 더 큰 도약이 될 것입니다 :

• -10, 0, 1
• -1000 ,

등 0 1000

-100000 0 100000

이 적은 프로브를 수행하지만, 더 많은 양분을 필요로한다. 소수의 다항식을 사용하고 두 제안이 모두있는 루트를 찾기 위해 실행 시간을 추적하십시오.

Answer 3

이분법 알고리즘을 사용하려면 먼저 루트가 포함 된 간격을 찾아야합니다.이에 대한 표준 알고리즘은 Sturm's Theorem에 나와 있습니다.

그러나 표준 이분 알고리즘은 끝점에서 함수 값의 부호가 다를 것으로 예상합니다. 이것은 문제가 될 수 있습니다. 가장 간단한 예는 x^2이며, 차수가 2 인 단일 루트 0을가집니다. x^2가 0이 아닌 x에 대해 모두 양수이므로 이진 알고리즘과 함께 사용하기에 적합한 루트를 둘러싸는 간격을 찾을 수 없습니다.

Answer 4

아마도 도움이 될 것입니다.

using System;

네임 스페이스는

{

class Program 

{ 

    public double midPoint (double xl, double xu) 

{ 

    return (xl + xu)/2; 

} 

    public double function(double x) 

    { 

     return (x*x-2); 

    } 

    static void Main(string[] args) 

    { 

     Program root = new Program(); 

     double xm=0, xl=1, xu=2, check=0; 

     for (int x = 0; x < 20; x++) 

     { 

      xm = (xl + xu)/2; 

      check = root.function(xl) * root.function(xm); 

      if (check < 0) 

       xu = xm; 

      else if (check > 0) 

       xl = xm; 

      else if (check == 0) 

      { 

       break; 

      } 

     } 

     Console.WriteLine("The Approximate of the Root is {0}", xm); 

    } 

} 

}

http://mustafa.amnbytes.com/2012/09/bisection-method-program-in-c.html