```python
import sympy as sp
import numpy as np
import pandas as pd
```


```python
x = sp.symbols('x')
f = sp.exp(2 * x)
```


```python
def calculate_first_derivative(nodes, values, forward=True):
    step = nodes[1] - nodes[0]
    diffs = []
    if forward:
        for i in range(len(nodes) - 1):
            diffs.append((values[i + 1] - values[i]) / step)
        diffs.append(None)
    else:
        diffs.append(None)
        for i in range(1, len(nodes)):
            diffs.append((values[i] - values[i - 1]) / step)
    
    return diffs
```


```python
def calculate_first_derivative_high_precision(nodes, values):
    step = nodes[1] - nodes[0]
    diffs = [None]
    for i in range(1, len(nodes) - 1):
        diffs.append((values[i + 1] - values[i - 1]) / (2 * step))
    diffs.append(None)
    return diffs
```


```python
def calculate_second_derivative(nodes, values):
    step = nodes[1] - nodes[0]
    diffs = [None]
    for i in range(1, len(nodes) - 1):
        diffs.append((values[i - 1] - 2 * values[i] + values[i + 1]) / step ** 2)
    diffs.append(None)
    return diffs
```


```python
def create_table_of_derivative_estimation(nodes, values, dvalues, d_est, d_est_hp, ddvalues, dd_est):
    derror = [abs(v - e) if e != None else None for v, e in zip(dvalues, d_est)]
    dhperror = [abs(v - e) if e != None else None for v, e in zip(dvalues, d_est_hp)]
    dderror = [abs(v - e) if e != None else None for v, e in zip(ddvalues, dd_est)]
    
    rows = list(zip(
        nodes, values,
        dvalues,
        d_est, derror,
        d_est_hp, dhperror,
        ddvalues,
        dd_est, dderror
    ))
    header = ['x', 'f(x)',
              'f\'(x)',
              'f\'(x) O(n) est.', 'f\'(x) O(n) error',
              'f\'(x) O(n^2) est.', 'f\'(x) O(n^2) error',
              'f\'\'(x)',
              'f\'\'(x) O(n^2) est.', 'f\'(x) O(n^2) error'
             ]
    return pd.DataFrame(rows, columns=header)
```

# 1


```python
a = 0
b = 4
nodes_count = 11
df = sp.diff(f)
ddf = sp.diff(df)

nodes = np.linspace(a, b, nodes_count, endpoint=True)
values = [f.evalf(subs={x: i}) for i in nodes]
dvalues = [df.evalf(subs={x: i}) for i in nodes]
ddvalues = [ddf.evalf(subs={x: i}) for i in nodes]

d_est = calculate_first_derivative(nodes, values)
d_est_hp = calculate_first_derivative_high_precision(nodes, values)
dd_est = calculate_second_derivative(nodes, values)
```


```python
create_table_of_derivative_estimation(nodes, values, dvalues, d_est, d_est_hp, ddvalues, dd_est)
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>x</th>
      <th>f(x)</th>
      <th>f'(x)</th>
      <th>f'(x) O(n) est.</th>
      <th>f'(x) O(n) error</th>
      <th>f'(x) O(n^2) est.</th>
      <th>f'(x) O(n^2) error</th>
      <th>f''(x)</th>
      <th>f''(x) O(n^2) est.</th>
      <th>f'(x) O(n^2) error</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.0</td>
      <td>1.00000000000000</td>
      <td>2.00000000000000</td>
      <td>3.06385232123117</td>
      <td>1.06385232123117</td>
      <td>None</td>
      <td>None</td>
      <td>4.00000000000000</td>
      <td>None</td>
      <td>None</td>
    </tr>
    <tr>
      <th>1</th>
      <td>0.4</td>
      <td>2.22554092849247</td>
      <td>4.45108185698494</td>
      <td>6.81872873975662</td>
      <td>2.36764688277168</td>
      <td>4.94129053049389</td>
      <td>0.490208673508958</td>
      <td>8.90216371396987</td>
      <td>9.38719104631362</td>
      <td>0.485027332343746</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.8</td>
      <td>4.95303242439511</td>
      <td>9.90606484879023</td>
      <td>15.1753598906162</td>
      <td>5.26929504182599</td>
      <td>10.9970443151864</td>
      <td>1.09097946639619</td>
      <td>19.8121296975805</td>
      <td>20.8915778771490</td>
      <td>1.07944817956855</td>
    </tr>
    <tr>
      <th>3</th>
      <td>1.2</td>
      <td>11.0231763806416</td>
      <td>22.0463527612832</td>
      <td>33.7733845411694</td>
      <td>11.7270317798862</td>
      <td>24.4743722158928</td>
      <td>2.42801945460959</td>
      <td>44.0927055225664</td>
      <td>46.4950616263828</td>
      <td>2.40235610381643</td>
    </tr>
    <tr>
      <th>4</th>
      <td>1.6</td>
      <td>24.5325301971094</td>
      <td>49.0650603942187</td>
      <td>75.1640495900872</td>
      <td>26.0989891958685</td>
      <td>54.4687170656283</td>
      <td>5.40365667140959</td>
      <td>98.1301207884374</td>
      <td>103.476662622295</td>
      <td>5.34654183385715</td>
    </tr>
    <tr>
      <th>5</th>
      <td>2.0</td>
      <td>54.5981500331442</td>
      <td>109.196300066288</td>
      <td>167.280668713977</td>
      <td>58.0843686476883</td>
      <td>121.222359152032</td>
      <td>12.0260590857435</td>
      <td>218.392600132577</td>
      <td>230.291547809724</td>
      <td>11.8989476771470</td>
    </tr>
    <tr>
      <th>6</th>
      <td>2.4</td>
      <td>121.510417518735</td>
      <td>243.020835037470</td>
      <td>372.289974768544</td>
      <td>129.269139731074</td>
      <td>269.785321741261</td>
      <td>26.7644867037907</td>
      <td>486.041670074940</td>
      <td>512.523265136419</td>
      <td>26.4815950614791</td>
    </tr>
    <tr>
      <th>7</th>
      <td>2.8</td>
      <td>270.426407426153</td>
      <td>540.852814852306</td>
      <td>828.546576114824</td>
      <td>287.693761262518</td>
      <td>600.418275441684</td>
      <td>59.5654605893785</td>
      <td>1081.70562970461</td>
      <td>1140.64150336570</td>
      <td>58.9358736610868</td>
    </tr>
    <tr>
      <th>8</th>
      <td>3.2</td>
      <td>601.845037872082</td>
      <td>1203.69007574416</td>
      <td>1843.96431630584</td>
      <td>640.274240561675</td>
      <td>1336.25544621033</td>
      <td>132.565370466167</td>
      <td>2407.38015148833</td>
      <td>2538.54435047754</td>
      <td>131.164198989210</td>
    </tr>
    <tr>
      <th>9</th>
      <td>3.6</td>
      <td>1339.43076439442</td>
      <td>2678.86152878884</td>
      <td>4103.81805661828</td>
      <td>1424.95652782944</td>
      <td>2973.89118646206</td>
      <td>295.029657673221</td>
      <td>5357.72305757767</td>
      <td>5649.63435078109</td>
      <td>291.911293203418</td>
    </tr>
    <tr>
      <th>10</th>
      <td>4.0</td>
      <td>2980.95798704173</td>
      <td>5961.91597408346</td>
      <td>None</td>
      <td>None</td>
      <td>None</td>
      <td>None</td>
      <td>11923.8319481669</td>
      <td>None</td>
      <td>None</td>
    </tr>
  </tbody>
</table>
</div>



# 2


```python
step = 1
target_node = 2
target_value = ddf.evalf(subs={x: target_node})
error = None

while True:
    nodes = [target_node - step, target_node, target_node + step]
    values = [f.evalf(subs={x: i}) for i in nodes]
    estimated_value = calculate_second_derivative(nodes, values)[1]
    new_error = round(abs(estimated_value - target_value), 5)
    
    if error == None or new_error <= error:
        error = new_error
        step /= 2
    else:
        break
```


```python
step
```




    3.0517578125e-05



# 3


```python
def newton_interpolation_equally_spaced_nodes(nodes, values, order):
    def finite_differences(nodes, values, max_order):
        if len(nodes) != len(values):
            raise ValueError("nodes and values lists must have the same length")
        diffs = [values]
        for order in range(max_order):
            current_diffs = []
            for i in range(1, len(nodes) - order):
                current_diffs.append(diffs[-1][i] - diffs[-1][i-1])
            diffs.append(current_diffs)
        return diffs
        
    step = nodes[1] - nodes[0]
    fds = finite_differences(nodes, values, order)

    t = (x - b) / step

    # Compute N_k for k up `order` to estimate error for polynom of order `order - 1`
    ns = [1]
    for i in range(order + 1):
        ns.append(ns[-1] * (t + i) / (i + 1))

    # Calculate all the polynoms with order from 0 to `order`
    polynoms = []
    for i in range(order + 1):
        prev = polynoms[-1] if len(polynoms) > 0 else 0
        polynoms.append(prev + ns[i] * fds[i][-1])

    return polynoms[-1]
```


```python
a, b = 0, 1
nodes_count = 11 # to include node `b` and have a nice 0.1 step
nodes = np.linspace(a, b, nodes_count, endpoint=True)
values = [f.evalf(subs={x: i}) for i in nodes]
new_node_id = 1

polynom = newton_interpolation_equally_spaced_nodes(nodes, values, 5)
```


```python
df_numeric = calculate_first_derivative(nodes, values)[new_node_id]
df_poly = sp.diff(polynom).evalf(subs={x: nodes[new_node_id]})
df_actual = sp.diff(f).evalf(subs={x: nodes[new_node_id]})
```


```python
df_actual, df_poly, df_numeric
```




    (2.44280551632034, 2.64068217834383, 2.70421939481100)




```python
poly_error, numeric_error = df_poly - df_actual, df_numeric - df_actual
poly_error, numeric_error
```




    (0.197876662023491, 0.261413878490665)



ec31488c6edc3bc933270dc9eefcc0e09a2f0497
ipynb
Jupyter Notebook
year-2/computational-workshop/task-5.ipynb
Sergobot/university
7cd8c07fc660f1e19127c6488991ddd59d99643c
MIT
2019-09-05T08:43:47.000Z
2019-09-05T08:43:52.000Z
year-2/computational-workshop/task-5.ipynb
Sergobot/university
7cd8c07fc660f1e19127c6488991ddd59d99643c
MIT
year-2/computational-workshop/task-5.ipynb
Sergobot/university
7cd8c07fc660f1e19127c6488991ddd59d99643c
MIT
2020-10-04T07:40:20.000Z
2021-09-18T07:12:08.000Z
Qwen/Qwen-72B
1. YES
2. YES