Determining the surface with given polynomial borders Let's say we'd like to guess the shape (I'm not sure the word 'approximate' is appropriate here) of some surface  when we are given its borders via third order polynomials (i.e. we are given their coefficients). To make things a bit simpler, let's assume we consider only a rectangle $[a,b]\times[c,d]$ - so if $f(x,y)$ is a function representing the sought surface, we have polynomials $f_1(x), \ f_2(x), \ f_3(y), \ f_4(y)$ of degree $3$ such that
$f(x,c) = f_1(x), \ f(x,d) = f_2(x), \ f(a,y) = f_3(y), \ f(b,y) = f_4(y)$.
Now, we'd like to have nice and easily calculable formula for $f$ that meets the criteria and is somehow smooth.
I thought that looking for $f$ in the bivariat polynomial form $$\sum_{0 \le i, j \le 3} \alpha_{i,j}x^iy^j$$
would be a good idea. Unfortunately, as I performed a few tests, it turns out that quite often it cannot be done - system of linear equations that emerge from constraints doesn't have a solution.
And my question is - what would be other 'human-friendly' form in which $f$ will always be expressible?
 A: A surface that interpolates its boundary curves is called a Coons patch. The Wikipedia page has a good description. There are many different variants, but the simplest is the one that uses bilinear blending, as described in the first section of the Wikipedia page. The discussion assumes $a=c=0$ and $b=d=1$, but you can easily rescale later, if you need to. 
We have to assume some compatibility conditions, otherwise the interpolation problem is unsolvable. Specifically, we need to assume that $f_1(a)=f_3(c)$, $f_1(b)=f_4(c)$, $f_2(a)=f_3(d)$, $f_2(b)=f_4(d)$.
Then, just construct the three-term interpolant as described on the Wikipedia page. The resulting function is infinitely differentiable, and interpolates the four boundary curves.
A tip: problems like this are usually much easier if you express the geometry in Bezier-Bernstein form, instead of using the polynomial (Taylor, power) basis. If you write your four boundary curves in Bezier form, then their control points give you 12 of the 16 control points required to construct a bicubic Bezier patch. The other four control points in the interior of the Bezier patch can actually be chosen arbitrarily, and you'll still get a surface that interpolates the boundary curves.
The technique you mentioned should have worked. Maybe you didn't assume the compatibility conditions I mentioned. Or, maybe things went wrong because the problem actually has an infinite number of solutions, as I mentioned in my comments on the Bezier patch approach.
