1
$\begingroup$

With Horner's algorithm, I can solve f(x$_{0}$) for a polynomial like this: $a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$

By doing this:

b$_n$ = a$_n$

b$_{n-1}$ = a$_{n-1}$ + b$_n$x$_0$

b$_{n-2}$ = a$_{n-2}$ + b$_{n-1}$x$_0$

...

b$_0$ = a$_0$ + b$_1$x$_0$

Where b$_0$ = f(x$_{0}$). The problem is doing Horner's algorithm on something like this: $a_1 + a_2(x + y_1) + a_3(x + y_1)(x + y_2) + a_4(x + y_1)(x + y_2)(x + y_3) + ... + a_{n+1}(x + y_1)(x + y_2)(x + y_3)...(x + y_n)$

So instead of a going from a$_0$ to a$_n$ it goes from a$_1$ to a$_{n+1}$ so for b$_n$, is it supposed to be b$_n$ = a$_{n+1}$? Also let's say we're trying to solve f(1.53) and we have:

a = -1, 3.3, 0, -2.2, 5, -1.6
y = -1, 1, -1, 1, -1

So if n = 5, this is how I did Horner's algorithm:

b$_5$ = -1.6

x$_0$ = (1.53 - 1)(1.53 + 1)(1.53 - 1)(1.53 + 1) = 1.79801281

b$_4$ = 5 + (-1.6)(1.79801281) = 2.123179504

x$_0$ = (1.53 - 1)(1.53 + 1)(1.53 - 1) = 0.710677

b$_3$ = -2.2 + (2.123179504)(0.710677) = -0.691105159

x$_0$ = (1.53 - 1)(1.53 + 1) = 1.3409

b$_2$ = 0 + (-0.691105159)(1.3409) = -0.926702907

x$_0$ = (1.53 - 1) = 0.53

b$_1$ = 3.3 + (-0.926702907)(0.53) = 2.808847459

b$_0$ = -1 + (2.808847459)(1.53) = 3.297536612

The problem is that f(1.53) = 6.65086 which is not what b$_0$ is so what am I doing wrong?

$\endgroup$
0
$\begingroup$

instead of a going from $a_0$ to $a_n$ it goes from $a_1$ to $a_{n+1}$ so for $b_n$, is it supposed to be b$_n$ = $a_{n+1}$?

The index needs adjusted, indeed. However, that's not the only change you need to make. Unlike in the case of Horner's method, the second expression is not a polynomial, since the terms do not contain consecutive powers of the same $\,x\,$. To account for that, the recurrence must be modified to:

$$ \begin{align} b_{n} &= a_{n+1} \\ b_{n-1} &= a_n + b_n(x+y_n) \\ b_{n-2} &= a_{n-1} + b_{n-1}(x+y_{n-1}) \\ &\cdots \\ b_{1} &= a_{2} + b_{2}(x+y_2) \\ b_{0} &= a_{1} + b_{1}(x+y_1) \\ \end{align} $$

The above is equivalent to writing the expression as:

$${\displaystyle a_{1}+(x+y_1)\bigg(a_{2}+(x+y_2)\Big(a_{3}+\cdots +(x+y_{n-1})\big(a_{n}+a_{n+1}(x+y_n)\big)\Big)\bigg)}$$

$\endgroup$
0
$\begingroup$

$$b_n=a_n $$

for $k $ from $n-1$ to $0$

$$b_k=a_k+b_{k+1}x_0$$

$\endgroup$
  • $\begingroup$ So are you saying that I should start with bn=an? Also am I right about x0? $\endgroup$ – Josh Susa Mar 4 '18 at 20:58
  • $\begingroup$ @JoshSusa you start from b_n=a_n and you compute successively b_{n-1}... untill b_0. $\endgroup$ – hamam_Abdallah Mar 4 '18 at 21:00
  • $\begingroup$ So then for my example, would I start by saying b5 = 5 and then b4 = -2.2 + (5)(1.3409)? $\endgroup$ – Josh Susa Mar 4 '18 at 21:13
  • $\begingroup$ @JoshSusa continue untill b_0 which is the result. $\endgroup$ – hamam_Abdallah Mar 4 '18 at 21:17
  • $\begingroup$ Yes I am aware of how Horner's algorithm works. My problem is using Horner's algorithm with the above polynomial. Using Horner's algorithm I got 3.29754 but f(1.53) = 6.65086 which means I must have done something wrong. Maybe I could post what I did and you can tell me where I went wrong? $\endgroup$ – Josh Susa Mar 4 '18 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.