<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <center>
    <img src="http
Step1:  <div id='intro' />
Introduction
Back to TOC
This jupyter notebook presents the notion of weigthed linear least square problems.
It first present the theoretical background, then a few small examples and finally makes a connection with the "Initial Example" from the section "Overdetermined Linear Systems of Equations" in the notebook "07_08_Least_Squares".
We strongly suggest the reader to review that example first.
<div id='wLeastSquare' />
Weighted least-square
Back to TOC
In this example we will consider we give a different weight to each term in the least square problem.
Mathematical, this can be seen as multiplying the least-square problem by a diagonal matrix, say $W=\text{diag}(w_1,w_2,\dots,w_m)$, with $w_i>0$.
For instance, consider the following least square example
Step2:  We clearly observe that the least square solutions are different!
This is consistent with the previous explanation.
<div id='extensionInitialExample' />
Extension of "Initial Example" in jupyter notebook "07_08_Least_Squares"
Back to TOC
In this example we will approximate $m$ points considering a linear relationship.
This means that we will have the data points $(x_i,y_i)$ for $i\in{1,2,\dots,m}$ and consider the relationshop $y=a_0+a_1\,b$.
The error that will be added follows a normal distribution, but we will consider we use the following weight matrix,
\begin{equation}
    W=\text{diag}(w,w,1,\dots,1).
\end{equation}
This means we will more weight to the first twio equations, this is arbitrarily, and it is only use to show what effects brings to the least square problem.
The example will only show the approximation output since we already saw all the other components in the original example.
Question to think before to modify the weight $w$
<ASSISTANT_TASK:>
Python Code:
import numpy as np
import matplotlib.pyplot as plt
import scipy.linalg as spla
%matplotlib inline
# https://scikit-learn.org/stable/modules/classes.html#module-sklearn.datasets
from sklearn import datasets
import ipywidgets as widgets
from ipywidgets import interact, interact_manual
import matplotlib as mpl
mpl.rcParams['font.size'] = 14
mpl.rcParams['axes.labelsize'] = 20
mpl.rcParams['xtick.labelsize'] = 14
mpl.rcParams['ytick.labelsize'] = 14
M=8
Explanation: <center>
    <img src="http://sct.inf.utfsm.cl/wp-content/uploads/2020/04/logo_di.png" style="width:60%">
    <h1> INF285 - Computación Científica </h1>
    <h2> Weigthed Least Squares </h2>
    <h2> <a href="#acknowledgements"> [S]cientific [C]omputing [T]eam </a> </h2>
    <h2> Version: 1.00</h2>
</center>
<div id='toc' />
Table of Contents
Introduction
Weighted least-square
Example in explanation
Extension of "Initial Example" in jupyter notebook "07_08_Least_Squares"
Acknowledgements
End of explanation
x1,x2,x3 = 1,2,3
y1,y2,y3 = 5,-1,3
A1 = np.ones((3,2))
A1[:,1]=[x1,x2,x3]
b1=np.array([y1,y2,y3])
A1[0,:]*=4
b1[0]*=4
x1_bar=np.linalg.solve(A1.T @ A1,A1.T @ b1)
print('A1: ', A1)
print('b1: ', b1)
print('x1_bar: ', x1_bar)
A2 = np.ones((3,2))
A2[:,1]=[x1,x2,x3]
b2=np.array([y1,y2,y3])
x2_bar=np.linalg.solve(A2.T @ A2,A2.T @ b2)
print('A2: ', A2)
print('b2: ', b2)
print('x2_bar: ', x2_bar)
Explanation: <div id='intro' />
Introduction
Back to TOC
This jupyter notebook presents the notion of weigthed linear least square problems.
It first present the theoretical background, then a few small examples and finally makes a connection with the "Initial Example" from the section "Overdetermined Linear Systems of Equations" in the notebook "07_08_Least_Squares".
We strongly suggest the reader to review that example first.
<div id='wLeastSquare' />
Weighted least-square
Back to TOC
In this example we will consider we give a different weight to each term in the least square problem.
Mathematical, this can be seen as multiplying the least-square problem by a diagonal matrix, say $W=\text{diag}(w_1,w_2,\dots,w_m)$, with $w_i>0$.
For instance, consider the following least square example:
\begin{equation}
    \underbrace{\begin{bmatrix}
        1 & x_1 \
        1 & x_2 \
        1 & x_3 \
        \vdots & \vdots \
        1 & x_m
    \end{bmatrix}}{\displaystyle{A}}
    \underbrace{\begin{bmatrix}
        a\
        b
    \end{bmatrix}}{\mathbf{x}}
    =
    \underbrace{\begin{bmatrix}
        y_1 \
        y_2 \
        y_3 \
        \vdots\
        y_m 
    \end{bmatrix}}{\displaystyle{\mathbf{b}}}.
\end{equation}
In this case, all the equations have the same weight.
Now, giving a different weight to each equation, we could do the following:
\begin{equation}
    \underbrace{W\,A}{\displaystyle{B}}\,\mathbf{x}=\underbrace{W\,\mathbf{b}}{\displaystyle{\mathbf{c}}},
\end{equation}
where, as mentioned before, we could define $W$ as follows,
\begin{equation}
    W=\text{diag}(w_1,w_2,\dots,w_m).
\end{equation}
So, when computing the quadratic error we obtain,
\begin{equation}
E=\left\|W\,\mathbf{b}- W\,A\,\mathbf{x}\right\|_2^2=\sum{i=1}^m w_i^2\,(y_i-a-b\,x_i)^2.
\end{equation}
This indicates that when we use a higher value of $w_i$ for some $i$'s, these equations will have a higher impact in the minimization.
From the normal equations point of view, this slightly modified problem will satisfy the following normal equations,
\begin{equation}
B^\,B\,\overline{\mathbf{x}}_w=B^\,\mathbf{c}.
\end{equation}
Notice that we used the sub-index $w$ for $\overline{\mathbf{x}}_w$ to differentiate it from the unweighted least square solution.
Thus, caming back to the original equations, we obtain,
\begin{align}
B^\,B\,\overline{\mathbf{x}}_w &=B^\,\mathbf{c},\
(W\,A)^\,(W\,A)\,\overline{\mathbf{x}}_w &=(W\,A)^\,W\,\mathbf{b},\
A^\,W^\,W\,A\,\overline{\mathbf{x}}_w &=A^\,W^\,W\,\mathbf{b},\
A^\,W^2\,A\,\overline{\mathbf{x}}_w &=A^\,W^2\,\mathbf{b},\
\overline{\mathbf{x}}_w &=(A^\,W^2\,A)^{-1}\,A^\,W^2\,\mathbf{b}.\
\end{align}
So, if $W$ is the identity matrix or a non-zero multiple of it, i.e. $W=\alpha\,I$ for $\alpha\neq0$, the weigthed least square problem reduces to,
\begin{align}
\overline{\mathbf{x}} &=(A^\,\alpha^2\,I^2\,A)^{-1}\,A^\,\alpha^2\,I^2\,\mathbf{b},\
\overline{\mathbf{x}} &=(A^\,A)^{-1}\,A^\,\mathbf{b}.\
\end{align}
It is important to point out that, from the least equare point of view, any algebraic modification we do to any equation, it will change its respective weight respect to the other equations.
For instance, if we have the following problem,
\begin{equation}
    \begin{bmatrix}
        4 & 4\,x_1 \
        1 & x_2 \
        1 & x_3
    \end{bmatrix}
    \begin{bmatrix}
        a\
        b
    \end{bmatrix}
    =
    \begin{bmatrix}
        4\,y_1 \
        y_2 \
        y_3 
    \end{bmatrix},
\end{equation}
it will have a different least square solution if we simplify the $4$ for the first equation.
This means, solving the following problem will lead to a different least square solution,
\begin{equation}
    \begin{bmatrix}
        1 & x_1 \
        1 & x_2 \
        1 & x_3
    \end{bmatrix}
    \begin{bmatrix}
        a\
        b
    \end{bmatrix}
    =
    \begin{bmatrix}
        y_1 \
        y_2 \
        y_3 
    \end{bmatrix}.
\end{equation}
The reason for this is that the generate different quadratic errors.
It is very important to hightlight that this weight effect is important because we are dealing with overdetermined linear system of equation.
In the case we deal with an square and non-singular linear system of equations this does not change the solution, for instance, the analysis changes to,
\begin{align}
B^\,B\,\mathbf{x} &= B^\,\mathbf{c},\
(W\,A)^\,(W\,A)\,\mathbf{x} &= (W\,A)^\,W\,\mathbf{b},\
A^\,W^\,W\,A\,\mathbf{x} &=A^\,W^\,W\,\mathbf{b},\
A^\,W^2\,A\,\mathbf{x} &=A^\,W^2\,\mathbf{b},\
\mathbf{x} &=(A^\,W^2\,A)^{-1}\,A^\,W^2\,\mathbf{b},\
\mathbf{x} &=A^{-1}\,W^{-2}\,A^{-}\,A^\,W^2\,\mathbf{b},\
\mathbf{x} &=A^{-1}\,W^{-2}\,\,W^2\,\mathbf{b},\
\mathbf{x} &=A^{-1}\,\mathbf{b}.\
\end{align}
The key difference is on the sixth line.
In this case there exists the inverse matrix of each matrix in the parenthesis, which was not true previously.
<div id='exampleExplanation' />
Example in explanation
Back to TOC
End of explanation
def showWeightedOutput(w=1):
    # Number of points to be used
    m = 10
    # Relationship considered
    fv = np.vectorize(lambda x, a0, a1: a0+a1*x)
    # Coefficients considered
    a0, a1 = 1, 4
    np.random.seed(0)
    # Standard deviation for the error
    sigma = 5e-1
    # Error to be added
    e = np.random.normal(0,sigma,m)
    # Generating data points
    x = np.linspace(0,1,m)
    y = fv(x,a0,a1)+e
    # Build the data matrix
    A = np.ones((m,2))
    A[:,1] = x
    # Setting up the right hand side
    b = np.copy(y)
    A[:2,:]*=w
    b[:2]*=w
    # Building and solving the normal equations
    # A^T A x_bar = A^T b
    x_bar = np.linalg.solve(A.T @ A, A.T @ b)
    # Showing the comparison between the "original function" and the "least-squared reconstructed approximation".
    # We added in red a "sample" of possible functions.
    # Notice that the colors used follow the description included in the classnotes.
    # This means to consider the following analogy:
    # blue: data points, this correspond to the right-hand-side vector "b".
    # red: this correspond to the sub-space generated by Ax, i.e. the span of the columns of A.
    # violet: This correspond to the least-square solution found.
    plt.figure(figsize=(10,10))
    for i in range(100):
        plt.plot(x,fv(x,x_bar[0]+np.random.normal(0,1),x_bar[1]+np.random.normal(0,1)),'r-',linewidth=1,alpha=0.2)
    plt.plot(x,fv(x,a0,a1),'k-',linewidth=8,alpha=0.8)
    plt.plot(x,fv(x,x_bar[0],x_bar[1]),'--',color='darkviolet',linewidth=4)
    plt.plot(x,fv(x,x_bar[0],x_bar[1]),'r.',markersize=20)
    plt.plot(x,y,'b.',markersize=10)
    plt.grid(True)
    plt.xlabel(r'$x$')
    plt.ylabel(r'$y$')
    plt.show()
interact_manual(showWeightedOutput,w=(0.01,101,0.01))
Explanation: We clearly observe that the least square solutions are different!
This is consistent with the previous explanation.
<div id='extensionInitialExample' />
Extension of "Initial Example" in jupyter notebook "07_08_Least_Squares"
Back to TOC
In this example we will approximate $m$ points considering a linear relationship.
This means that we will have the data points $(x_i,y_i)$ for $i\in{1,2,\dots,m}$ and consider the relationshop $y=a_0+a_1\,b$.
The error that will be added follows a normal distribution, but we will consider we use the following weight matrix,
\begin{equation}
    W=\text{diag}(w,w,1,\dots,1).
\end{equation}
This means we will more weight to the first twio equations, this is arbitrarily, and it is only use to show what effects brings to the least square problem.
The example will only show the approximation output since we already saw all the other components in the original example.
Question to think before to modify the weight $w$: What would you expect to happen with the approximation if you use a large value for $w$?
End of explanation
<END_TASK>