이진법을 사용하여 솔루션을 찾기위한 반복 횟수 이해하기

Question

이진법을 사용하여 방정식의 근원을 찾고 파이썬 3을 사용하는 for 루프 만 찾았습니다. This 스레드는이 방법을 사용하는 방법을 보여줍니다. 숫자에 대한 설명은 range()입니다. 2 * X - -

예로서, I는 X = ² 함수

F (x)를 가지고 3

및 I로 시작하는, 부정적인 루트를 찾을 간격 [-4, 1].

루프를 사용하여 for 루프를 사용하여 함수를 작성했지만 사용 범위 또는 사용 방법을 이해하지 못했습니다. 여기

문제 해결 내 코드이다 : 프로그램이 작동하는지 확인

... 
a = -4 
b = 1 
c = (a + b)/2 

for i in range(1000): 
    if f(c) == 0: 
     break 
    if f(a) * f(c) < 0: 
     b = c 
    elif f(a) * f(c) > 0: 
     a = c 
    c = (a + b)/2 

return c, f(c), i 

C = -1 (찾았 음 루트), F (C) = 0, 그리고 나타내는 전 52 = 52 개의 "2 분법"을 시도한 후에 올바른 답을 찾았습니다.

range()에 매우 큰 숫자를 넣어 루트를 찾았지만 왜 52 번의 반복이 필요합니까?

플러스, 내 간격을 [-2, 1] (으)로 변경하면 53 회 시도해야합니다. 그 이유는 무엇입니까?

Answer 1

는 :

[-4, 1] 
[-1.5, 1] 
[-1.5, -0.25] 
[-1.5, -0.875] 
[-1.1875, -0.875] 
[-1.03125, -0.875] 
... 
... 
... 
[-1.0000000000000284, -0.9999999999999929] 
[-1.0000000000000107, -0.9999999999999929] 
[-1.0000000000000018, -0.9999999999999929] 
[-1.0000000000000018, -0.9999999999999973] 
[-1.0000000000000018, -0.9999999999999996] 
[-1.0000000000000007, -0.9999999999999996] 

-1.0000000000000007 및 -0.9999999999999996의 계산 된 평균 정확히 -1입니다. 왜? 수레가 표현할 수있는 것의 한계에 도달했기 때문입니다.

>>> '%.60f' % -1.0000000000000007 
'-1.000000000000000666133814775093924254179000854492187500000000' 

>>> '%.60f' % -0.9999999999999996 
'-0.999999999999999555910790149937383830547332763671875000000000' 

>>> '%.60f' % (-1.0000000000000007 + -0.9999999999999996) 
'-2.000000000000000000000000000000000000000000000000000000000000' 

>>> '%.60f' % ((-1.0000000000000007 + -0.9999999999999996)/2) 
'-1.000000000000000000000000000000000000000000000000000000000000' 

수레 저장소 52 bits of fraction, 선두 1 비트 후의 52 비트를 의미한다 : 여기 관련된 정확한 값이다. 약 1/2보다 작은 것을 잃는다는 것을 의미합니다. 값입니다. 52 단계를 거치면 초기 크기 범위는 5/2 크기가됩니다 . 약 1/2의 입니다. 그래서 주변에, 부정확 때문에 정확히 -1에 비틀 거리는 꽤 좋은 기회에 도달합니다.

5/2 이 여전히 1/2 보다 약간 크기 때문에 2 단계 또는 3 단계 더 걸릴 수 있습니다. 운이 좋았어. 다른 초기 범위 [-2, 1]을 사용하면 운이 좋지 않게됩니다. -1에 도달하기 전에 범위가 [-1.0000000000000002, -0.9999999999999999]까지 축소됩니다.

[-4000000, 1]으로 시작하면 72 단계가 필요합니다. 초기 범위가 백만 배 더 크므로 20 단계 더 많습니다. 이는 약 2 입니다.

다른 경우 : 기능 x**2 - 1000000과 초기 범위 [999.3, 1000.3]을 사용하는 경우 41 단계가 필요합니다. 왜? 최종 값 (즉, 근음)은 1000이고 초기 범위는 크기 1입니다. 1/1000이므로 약 1/2/입니다. 따라서 1/2에 이르려면 만 있으면 약 42 개의 이분법이 필요합니다.

Answer 2

반복 할 때마다 검색 간격을 절반으로 줄입니다. 각 반복마다 컴퓨터의 부동 소수점 표현의 정확도 내에서 중간 점의 함수 값 f (c)가 0인지 확인합니다.

[-101, 99] 간격을 선택하는 경우 c = -1을 명중 할 때와 같이 해법을 하나만 얻을 수 있습니다. 프로그램이 실제 루트에 가까워 질 때마다 평가가 시작될 때마다 프로그램이 중지됩니다. 0.000000

너비 5의 범위에서 시작 했습니까? 2, 52로 나누는 것은 무엇입니까? 구현시 부동 소수점 숫자의 정확도는 어떻게됩니까? 나는 두 개의 플로트 사이의 최소 차이에 가깝다고 확신 할 것입니다.

당신이 정말로 오른쪽 상단에, 행동에서 볼 루프 내부에 하나 개의 간단한 라인을 추가하려면

는 :

print a, b, c, f(c) 

이렇게하면 루트를 찾는 과정을 보여줍니다.

인쇄 문은 프로그램을 추적하는 기술이 부족하고 효과적인 방법입니다.

COMMENT의 응답

좋은 점 : 나는 충분히 열심히 특정 케이스를 호출하지 않았습니다.

52 번의 반복 작업이 끝났습니다. 프로그램이 올바른 값을 가로 질러 "넘어지기"위해 걸린 횟수가 많기 때문입니다. 작은 범위에서 53 번 반복하여 변경하고 만들 때 ... 간단한 방법은 처음에는 조금 운이 좋다는 것입니다.이으로 나타 났으므로 [-101, 99]와 같이 중점으로 -1이있는 것으로 시작하면 훨씬 더 큰 간격을 가지고 있음에도 불구하고 하나의 반복 만 완료하게됩니다. 당신이 print([a, b]) 루프에서, 당신은 범위의 진화를 볼 수 있다면