50166. Newton's Method

I'm a slow walker, but I never walk backwards.

Task Description

Implement Newton's method, which is a root-finding algorithm.
Let $f$ be a differentiable function defined on the interval (a, b).
To simplify the task we will assume that $f$ is a polynomial of $x$.
We start with $x_{1}$ and find the line at $(𝑥_{1} ,ƒ(𝑥_{1}))$ with slope $f'(x_{1})$.
This line will intersect with the $x$-axis at $(x_{2}, 0)$.
We then repeat this procedure to find $x_{3}, x_{4}$, and so on.
Please refer to the following illustration.

Your program will iterate Newton's method for k times and output $𝑥_{k}$ and $ƒ(𝑥_{k})$ in each iteration.

Input Format

There are four lines in the input.
The first line is the degree $d$ of polynomial.

  • $1 \lt d \lt 10$

The second line contains the coefficients of the polynomial and each of them should be double.
For example: $1.54𝑥^3 +3.88𝑥 -4.742$ is denoted as 1.54 0.0 3.88 -4.742.

The third line is the maximum iteration $k$.

  • $0 \lt k \lt 1000$

The last line is $𝑥_{1}$. It should be double.

Output Format

You need to output $x_{i}$ and $f(x_{i})$ for every iteration. Please "%.4f" in printf function to output the answers.

Sample Input 1

3
1.54 0.0 3.88 -4.742
13
30.999

Sample Output 1

30.9990 45989.2344
20.6490 13634.1107
13.7414 4044.4273
9.1258 1201.0452
6.0353 357.2201
3.9604 106.2858
2.5682 31.3084
1.6568 8.6899
1.1321 1.8849
0.9398 0.1825
0.9168 0.0023
0.9166 0.0000
0.9166 0.0000

Discussion