Editing Bilinear interpolation (section)

==Computation==
[[Image:BilinearInterpolationV2.svg|right|thumb|The four red dots show the data points and the green dot is the point at which we want to interpolate.]]

Suppose that we want to find the value of the unknown function ''f'' at the point (''x'', ''y''). It is assumed that we know the value of ''f'' at the four points ''Q''<sub>11</sub> = (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>), ''Q''<sub>12</sub> = (''x''<sub>1</sub>,&nbsp;''y''<sub>2</sub>), ''Q''<sub>21</sub> = (''x''<sub>2</sub>,&nbsp;''y''<sub>1</sub>), and ''Q''<sub>22</sub> = (''x''<sub>2</sub>,&nbsp;''y''<sub>2</sub>).

===Repeated linear interpolation ===
We first do linear interpolation in the ''x''-direction. This yields
:<math>\begin{align}
  f(x, y_1) = \frac{x_2-x}{x_2-x_1} f(Q_{11}) + \frac{x-x_1}{x_2-x_1} f(Q_{21}), \\
  f(x, y_2) = \frac{x_2-x}{x_2-x_1} f(Q_{12}) + \frac{x-x_1}{x_2-x_1} f(Q_{22}).
\end{align}</math>

We proceed by interpolating in the ''y''-direction to obtain the desired estimate:
:<math>\begin{align}
  f(x,y) &= \frac{y_2-y}{y_2-y_1} f(x, y_1) + \frac{y-y_1}{y_2-y_1} f(x, y_2) \\
         &= \frac{y_2-y}{y_2-y_1} \left( \frac{x_2-x}{x_2-x_1} f(Q_{11}) + \frac{x-x_1}{x_2-x_1} f(Q_{21}) \right) +
            \frac{y-y_1}{y_2-y_1} \left( \frac{x_2-x}{x_2-x_1} f(Q_{12}) + \frac{x-x_1}{x_2-x_1} f(Q_{22}) \right) \\
         &\begin{aligned}[b]
= \frac{1}{(x_2-x_1)(y_2-y_1)} ( &f(Q_{11})(x_2-x)(y_2-y) + f(Q_{12})(x_2-x)(y-y_1)\\
& + f(Q_{21})(x-x_1)(y_2-y) + f(Q_{22})(x-x_1)(y-y_1))
\end{aligned} \\
         &= \frac{1}{(x_2-x_1)(y_2-y_1)} \begin{bmatrix} x_2-x & x-x_1 \end{bmatrix} \begin{bmatrix} f(Q_{11}) & f(Q_{12}) \\ f(Q_{21}) & f(Q_{22}) \end{bmatrix} \begin{bmatrix}
y_2-y \\ y-y_1 \end{bmatrix}.
\end{align}</math>

Note that we will arrive at the same result if the interpolation is done first along the ''y'' direction and then along the ''x'' direction.<ref>{{cite book |last1=Press |first1=William H. |last2=Teukolsky |first2=Saul A. |last3=Vetterling |first3=William T. |last4=Flannery |first4=Brian P. |title=Numerical recipes in C: the art of scientific computing |date=1992 |publisher=Cambridge University Press |location=New York, NY, USA |isbn=0-521-43108-5 |pages=[https://archive.org/details/numericalrecipes0865unse/page/123 123-128] |edition=2nd |url=https://archive.org/details/numericalrecipes0865unse/page/123 }}</ref>

===Polynomial fit===
An alternative way is to write the solution to the interpolation problem as a [[multilinear polynomial]]

:<math>f(x, y) \approx a_{00} + a_{10}x + a_{01}y + a_{11}xy,</math>
where the coefficients are found by solving the linear system

:<math>\begin{align}
\begin{bmatrix}
1 & x_1 & y_1 & x_1 y_1 \\
1 & x_1 & y_2 & x_1 y_2 \\
1 & x_2 & y_1 & x_2 y_1 \\
1 & x_2 & y_2 & x_2 y_2 
\end{bmatrix}\begin{bmatrix}
a_{00}\\a_{10}\\a_{01}\\a_{11}
\end{bmatrix} = \begin{bmatrix}
f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})
\end{bmatrix},
\end{align}</math>

yielding the result
:<math>\begin{align}
\begin{bmatrix}
a_{00}\\a_{10}\\a_{01}\\a_{11}
\end{bmatrix} = \frac{1}{(x_2-x_1)(y_2-y_1)}\begin{bmatrix}
x_2y_2 & -x_2y_1 & -x_1y_2 & x_1y_1 \\
-y_2 & y_1 & y_2 & -y_1 \\
-x_2 & x_2 & x_1 & -x_1 \\
1 & -1 & -1 & 1 
\end{bmatrix}\begin{bmatrix}
f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})
\end{bmatrix}.
\end{align}</math>

=== Weighted mean ===
[[File:Bilinear interpolation visualisation.svg|thumb|upright|A geometric visualisation of bilinear interpolation. The product of the value at the desired point (black) and the entire area is equal to the sum of the products of the value at each corner and the partial area diagonally opposite the corner (corresponding colours).]]
The solution can also be written as a [[Weighted Mean|weighted mean]] of the ''f''(''Q''):
:<math>f(x, y) \approx w_{11} f(Q_{11}) + w_{12} f(Q_{12}) + w_{21} f(Q_{21}) + w_{22} f(Q_{22}),</math>

where the weights sum to 1 and satisfy the transposed linear system
:<math>
  \begin{bmatrix}
    1       & 1         & 1         & 1         \\
    x_1     & x_1       & x_2       & x_2       \\
    y_1     & y_2       & y_1       & y_2       \\
    x_1y_1  & x_1y_2    & x_2y_1    & x_2y_2
\end{bmatrix}
\begin{bmatrix}
    w_{11} \\ w_{12} \\ w_{21} \\ w_{22}
\end{bmatrix} =
\begin{bmatrix}
    1 \\ x \\ y \\ xy
\end{bmatrix},
</math>

yielding the result
:<math>\begin{align}
\begin{bmatrix}
w_{11}\\w_{21}\\w_{12}\\w_{22}
\end{bmatrix} = \frac{1}{(x_2-x_1)(y_2-y_1)}\begin{bmatrix}
x_2y_2 & -y_2 & -x_2 & 1 \\
-x_2y_1 & y_1 & x_2 & -1 \\
-x_1y_2 & y_2 & x_1 & -1 \\
x_1y_1 & -y_1 & -x_1 & 1 
\end{bmatrix}\begin{bmatrix}
1\\x\\y\\xy
\end{bmatrix},
\end{align}</math>
which simplifies to
:<math>\begin{align}
  w_{11} &= \frac{(x_2 - x  )(y_2 - y  )}{(x_2 - x_1)(y_2 - y_1)}, \\
  w_{12} &= \frac{(x_2 - x  )(y   - y_1)}{(x_2 - x_1)(y_2 - y_1)}, \\
  w_{21} &= \frac{(x   - x_1)(y_2 - y  )}{(x_2 - x_1)(y_2 - y_1)}, \\
  w_{22} &= \frac{(x   - x_1)(y   - y_1)}{(x_2 - x_1)(y_2 - y_1)},
\end{align}</math>
in agreement with the result obtained by repeated linear interpolation. The set of weights can also be interpreted as a set of [[generalized barycentric coordinates]] for a rectangle.

=== Alternative matrix form ===
Combining the above, we have
:<math>\begin{align}
f(x,y) \approx \frac{1}{(x_2-x_1)(y_2-y_1)}
\begin{bmatrix}f(Q_{11}) & f(Q_{12}) & f(Q_{21}) & f(Q_{22})\end{bmatrix}\begin{bmatrix}
x_2y_2 & -y_2 & -x_2 & 1 \\
-x_2y_1 & y_1 & x_2 & -1 \\
-x_1y_2 & y_2 & x_1 & -1 \\
x_1y_1 & -y_1 & -x_1 & 1 
\end{bmatrix}\begin{bmatrix}
1\\x\\y\\xy
\end{bmatrix}.
\end{align}</math>

=== On the unit square ===
If we choose a coordinate system in which the four points where ''f'' is known are (0,&nbsp;0), (0,&nbsp;1), (1,&nbsp;0), and (1,&nbsp;1), then the interpolation formula simplifies to 
:<math>f(x, y) \approx f(0, 0) (1 - x)(1 - y) + f(0, 1) (1 - x)y + f(1, 0) x(1 - y) + f(1, 1) xy, </math>

or equivalently, in matrix operations:
:<math>f(x, y) \approx \begin{bmatrix} 1 - x & x \end{bmatrix} \begin{bmatrix} f(0, 0) & f(0, 1) \\ f(1, 0) & f(1, 1) \end{bmatrix} \begin{bmatrix} 1 - y \\ y \end{bmatrix}.</math>

Here we also recognize the weights:
:<math>\begin{align}
  w_{11} &= (1 - x)(1 - y), \\
  w_{12} &= (1 - x)y, \\
  w_{21} &= x(1 - y), \\
  w_{22} &= xy.
\end{align}</math>
Alternatively, the interpolant on the unit square can be written as
:<math>f(x, y) = a_{00} + a_{10}x + a_{01}y + a_{11}xy,</math>

where 
:<math>\begin{align}
  a_{00} &= f(0, 0), \\
  a_{10} &= f(1, 0) - f(0, 0), \\
  a_{01} &= f(0, 1) - f(0, 0), \\
  a_{11} &= f(1, 1) - f(1, 0) - f(0, 1) + f(0, 0).
\end{align}</math>

In both cases, the number of constants (four) correspond to the number of data points where ''f'' is given.