There are two main methods for least squares ellipse fitting:
1) Minimise algebraic distance, i.e. minimise sum(F(x)^2) subject to some constraint, where F(x) = x'Ax + b'x + c
This is a linear least squares problem, and thus cheap to compute. There are many different possible constraints, and these produce different fits. fitellipse supplies two:
[z, a, b, al] = fitellipse(x, 'linear')
[z, a, b, al] = fitellipse(x, 'linear', 'constraint', 'trace')
See published demo file for more information.
2) Minimise geometric distance - i.e. the sum of squared distance from the data points to the ellipse. This is a more desirable fit, as it has some geometric meaning. Unfortunately, it is a nonlinear problem and requires an iterative method (e.g. Gauss Newton) to solve it. This is implemented as the default option in fitellipse. If it fails to converge, it fails gracefully (with a warning), returning the linear least squares estimate used to derive the start value

[z, a, b, alpha] = fitellipse(x)

plotellipse(z, a, b, alpha) can be used to plot the fitted ellipses